(Elementary number theory) Understanding congruence and modulus

9 replies · 2K views · last reply
Leo Liu
Messages
353
Reaction score
156
TL;DR
N/A
Handwritten-style worked solution computing 3^47 mod 7 as a chain of congruences, with red numerals 1 and 2 marking the step from 9(3^3)^15 to 2(-1)^15 (mod 7) and the final result 5 (mod 7).


In this question, how does the step marked with 1 become the step marked with 2? I can see that the transitivity property of congruence is used, but I don’t know what exactly is going on here. Can someone please explain? Also at which step is Congruence Add and Multiply used?

Thanks.

Preposition used:
Typeset statement of Proposition 3, Congruence Add and Multiply (CAM): for integers a_i and b_i with a_i ≡ b_i (mod m) for 1 ≤ i ≤ n, then 1. a_1 + a_2 + ... + a_n ≡ b_1 + b_2 + ... + b_n (mod m), and 2. a_1 a_2 ... a_n ≡ b_1 b_2 ... b_n (mod m).
 
jedishrfu said:
Isn’t 9 mod 7 the value 2?

Similarly for 3^3 is 27 which is one less than 28.
Yes. But I just don't understand how the theorem is applied here.
 
The theorem says the modulo N of a sum or product of a list of numbers is the same as the sum or product of the modulos of those numbers, right?
 
  • Like
Likes   Reactions: Leo Liu
jedishrfu said:
The theorem says the modulo N of a sum or product of a list of numbers is the same as the sum or product of the modulos of those numbers, right?
Right. But I am afraid that I still cannot see why as the congruence equations are not in the same form as the preposition.
 
Leo Liu said:
Right. But I am afraid that I still cannot see why as the congruence equations are not in the same form as the preposition.
What does that mean?

We have ##9 = 2 + 7##. Therefore ##9 \equiv 2 \ (mod \ 7)##. Therefore we may replace ##9## by ##2## in any equation modulo ##7##. That's the idea.
 
  • Skeptical
Likes   Reactions: Leo Liu
The proposition says that if ##a_1\equiv a_2 \; (mod\; m)## and ##b_1\equiv b_2 \; (mod\; m)##, then you have ##a_1b_1\equiv a_2b_2 \; (mod\; m)##.

In the example it is applied to ##9 \equiv 2 \; (mod\; 7)## and ##3^3 \equiv -1 \; (mod\; 7)##.
 
  • Like
Likes   Reactions: Leo Liu
PeroK said:
What does that mean?

We have ##9 = 2 + 7##. Therefore ##9 \equiv 2 \ (mod \ 7)##. Therefore we may replace ##9## by ##2## in any equation modulo ##7##. That's the idea.
Thanks. You answer helped me understand it intuitively. Yet I still don't know how the congruence add and multiply is applied to this step.
 
martinbn said:
The proposition says that if ##a_1\equiv a_2 \; (mod\; m)## and ##b_1\equiv b_2 \; (mod\; m)##, then you have ##a_1b_1\equiv a_2b_2 \; (mod\; m)##.

In the example it is applied to ##9 \equiv 2 \; (mod\; 7)## and ##3^3 \equiv -1 \; (mod\; 7)##.
This makes sense, but could you explain why this expression still holds when a1 and b1 is followed by (mod m)?
 
Leo Liu said:
Thanks. You answer helped me understand it intuitively. Yet I still don't know how the congruence add and multiply is applied to this step.
Proposition 3 that you quoted in your OP is a formal way to say you can replace a number by any other number of modular equivalence in products and sums. That's what it means - and Proposition 3 is that idea written out formally.
 
  • Like
Likes   Reactions: Leo Liu