1
$\begingroup$

In one of my classes, the following approach was shown to solve modulo operations involving huge numbers:

Problem to solve:

49 10 mod 187.

Approach taken:

  1. Prime factorize $187$. It's factors are $11$ and $17$.
  2. Find 49 10 mod 11, which involves:
    • Replacing 49 10 mod 11 as 5 10 mod 11
    • 5 10 mod 11 => 1 mod 11 => 1 (Using fermat's little theorem)
  3. Find 49 10 mod 17, which involves:
    • Replacing 49 10 mod 17 as 15 10 mod 17
    • 15 10 mod 17 => 4 (Can be solved using repeated exponents approach)
  4. Find a number which yields remainder of $1$ when divided by $11$ (step-2) and which yields remainder of $4$ when divided by $17$. For ex: $\{4,21,38,55,72,89...\}$ In this set $89$ is such a number.
  5. Hence it was concluded that 89 is the solution of 49 10 mod 11

What I understood in the above approach I got the parts of solving the prime factored modulo versions using fermets and repeated powering.

What I am failing to understand in the above approach

  1. How does this approach work, like modulo of a number (n) by its individual prime factors (p,q) leading to the modulo of a number (n) by (pq).

  2. Replacement of 49 10 mod 11 as 5 10 mod 11. I believe 5 and 49 are in the same congruence classes of modulo 11. Considering that what are the conditions in which such a replacement is valid?

I am new to this topic, so please try to explain in simple terms and provide some examples to help me understand this.

Thanks for your help.

$\endgroup$
  • $\begingroup$ First of all, the guy's name is Fermat. If you know about basic ring theory (of integers) you might want to look into the Chinese Remainder Theorem. This is a classical application of it, and answers your question. Concerning your second question: This follows from the fact that taking a number modulo $11$ (or any other number) commutes with sums and products, e.g. ab mod 11 is the same as taking the product of a mod 11 and b mod 11 (and reducing the product modulo 11 again) Again this is basic ring theory (of integers) $\endgroup$ – kesa Feb 15 '18 at 9:29
  • $\begingroup$ As @kesa says, this is a Chinese Remainder Theorem application. I'll point out that in your step 3, you can replace $15$ by $-2$ and make the calculation easier. $(-2)^4 \equiv 1 \pmod{17}.$ $\endgroup$ – B. Goddard Feb 15 '18 at 11:40
  • $\begingroup$ @B.Goddard although it doesn't change the $(-2)^{10}$ result, I'll note that $(-2)^4\equiv -1 \bmod 17$. $\endgroup$ – Joffan Feb 16 '18 at 7:26

Your Answer

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

Browse other questions tagged or ask your own question.