What is the solution of the following congruency

Question

Well, I tried to solve this equation. I think, that I have to work with the Chinese remainder theorem.

$$73x \equiv 1 \pmod{247} $$

$247=13×19$ so I may have to check the modulo $13$ and modulo $19$ congruences, but I really don't know, how to solve it.

If you can, help me please. Thank you very much.

Answer 1

A solution to the congruency problem: 73x≡1 (mod 247).

Here is a link to a PDF file for my solution: http://www.aespen.ca/AEnswers/1415499627.pdf.

The image below was generated from the PDF file:

Answer 2

Hint: $\gcd(73,247)=1$ Can you write the gcd as a linear combination?

Answer 3

You have to apply the Extended Euclidean Algorithm to find the modular inverse of $73 \mod{247}$, which is denoted $(73)^{-1}\pmod{247}$.

First verify that $\gcd(73,247) = 1$. You've basically already done the work since $73$ is prime and doesn't match either of the two prime factors of $247$. This affirms that you can apply the algorithm to find the modular inverse of $73$.

As to how to actually go about doing it, there are many pen and paper implementations. The one I favour is something called the "magic box" method. You can find out more by a quick google. Quite a few steps are required, but it's basically simple division while keeping track of the remainder, and you'll quickly be able to deduce that:

$(-13)\cdot 247 + (44)\cdot 73 = 1$

So when you're working modulo $247$, you get:

$0 + (44)\cdot 73 = 1$

which means that $(73)^{-1} \equiv 44 \pmod{247}$.

So your solution is $x = 44 \pmod{247}$.