cj104
Badges: 11
Rep:
?
#1
Report Thread starter 1 month ago
#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
reply
ghostwalker
  • Study Helper
Badges: 17
#2
Report 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
reply
DFranklin
Badges: 18
Rep:
?
#3
Report 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
reply
old_engineer
Badges: 11
Rep:
?
#4
Report 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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

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%

Watched Threads

View All
Latest
My Feed