The Student Room Group

Congruence: Squaring both sides

So, if we were to find the remainder of 364 over 7 we could do:
3 ≅ r (mod 7)
3 ≅ 3 (mod 7)
32 ≅ 32 (mod 7) = 2 (mod 7)
(edited 1 year ago)
Original post by cj104
So, if we were to find the remainder of 364 over 7 we could do:
3 ≅ r (mod 7)
3 ≅ 3 (mod 7)
32 ≅ 32 (mod 7) = 2 (mod 7)
... we repeat this until eg:
364 ≅ 22 (mod 7)
where the number is too big to just plug into the calculator and find the remainder as I did with the 2 (mod 7).
Any help to what can I do here?


Fermat's Little Theorem would help here.
Original post by cj104
So, if we were to find the remainder of 364 over 7 we could do:
3 ≅ r (mod 7)
3 ≅ 3 (mod 7)
32 ≅ 32 (mod 7) = 2 (mod 7)
... we repeat this until eg:
364 ≅ 22 (mod 7)
where the number is too big to just plug into the calculator and find the remainder as I did with the 2 (mod 7).
Any help to what can I do here?

FLT is one option, as 64 is a power of 2 you can also just repeatedly square and reduce mod 7 at each step.

E.g. to find: 2^64 mod 13
2^2 = 4 (mod 13)
2^4 = (2^2)^2 = 16 = 3 (mod 13)
2^8 = (2^4)^2 = 3^2 = 9 (mod 13)
2^16 = (2^8)^2 = 9^2 = 81 = 3 (mod 13)
2^32 = 9 (mod 13)
2^64 = 3 (mod 13)

[In this case FLT is undoubtedly easier, but when the prime is much larger than 7, even after applying FLT you still have numbers too big to handle directly and you need to use a method such as this].
Original post by DFranklin
FLT is one option, as 64 is a power of 2 you can also just repeatedly square and reduce mod 7 at each step.

E.g. to find: 2^64 mod 13
2^2 = 4 (mod 13)
2^4 = (2^2)^2 = 16 = 3 (mod 13)
2^8 = (2^4)^2 = 3^2 = 9 (mod 13)
2^16 = (2^8)^2 = 9^2 = 81 = 3 (mod 13)
2^32 = 9 (mod 13)
2^64 = 3 (mod 13)

[In this case FLT is undoubtedly easier, but when the prime is much larger than 7, even after applying FLT you still have numbers too big to handle directly and you need to use a method such as this].

...and just to add another variant method, it is sometime possible, simply by trial and error, to find a manageable power of 2 (to reuse @DFranklin's example) that is equal to 1 (mod 13) or -1 (mod 13). It so happens that 2^6 = -1 (mod 13).
Then 2^60 = (2^6)^10 = (-1)^10 (mod 13) = 1 (mod 13), from which 2^64 = 2^4 x 1 (mod 13) = 16 (mod 13) = 3 (mod 13).

Similar working is possible starting with 2^12 = 1 (mod 13).

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you