2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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:

enter image description here

$\endgroup$
  • $\begingroup$ thank you very much for your help $\endgroup$ – Herrpeter Nov 12 '14 at 10:16
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thank you very much for your help:) $\endgroup$ – Herrpeter Nov 5 '14 at 7:40
  • $\begingroup$ I would have only one quetion. I don't understand the lest step, can you explain it maybe? Thank you... $\endgroup$ – Herrpeter Nov 5 '14 at 8:02
  • $\begingroup$ 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? $\endgroup$ – Deepak Nov 5 '14 at 8:30
  • $\begingroup$ yes it's clear now, thank you very much for your help. $\endgroup$ – Herrpeter Nov 5 '14 at 8:54
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.