What is the solution of the following congruency 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.
 A: 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}$.
A: Hint: $\gcd(73,247)=1$ Can you write the gcd as a linear combination?
A: 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:

