# 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 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:

• thank you very much for your help – Herrpeter Nov 12 '14 at 10:16

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}$.

• thank you very much for your help:) – Herrpeter Nov 5 '14 at 7:40
• I would have only one quetion. I don't understand the lest step, can you explain it maybe? Thank you... – Herrpeter Nov 5 '14 at 8:02
• You mean the step where I put a $0$? I am taking the equation $(-13)\cdot 247 + (44)\cdot 73 = 1$ and then working modulo $247$. Remember that any multiple of $247$ becomes zero when you do this. This allows you to show that $(44)\cdot 73 = 1 \pmod {247}$ (I omitted the modulo notation because I had already stated that I was working modulo $247$ in the previous line). But I've corrected that small detail now. Does that make sense now? – Deepak Nov 5 '14 at 8:30
• yes it's clear now, thank you very much for your help. – Herrpeter Nov 5 '14 at 8:54

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

• after the euklid algorithm? – Herrpeter Nov 5 '14 at 7:39
• Yes. The Chinese Remainder Theorem is used for a system of congruences, so it can't be used here, – Swapnil Tripathi Nov 5 '14 at 7:40
• thank you very much also for your help, have a nice day. – Herrpeter Nov 5 '14 at 7:41