# Congruence: Squaring both sides

Watch
Announcements
#1
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?
0
1 month ago
#2
(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.
0
1 month ago
#3
(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].
0
1 month ago
#4
(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).
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### Poll

Join the discussion

#### Do you have the space and resources you need to succeed in home learning?

Yes I have everything I need (195)
58.21%
I don't have everything I need (140)
41.79%