I came across a question which uses Fermat's little theorem:
The Question:
Find a positive integer n such that \(7n^{25}\) - 10 is divisible by 83.
The Solution given in the book:
Since 7 x 37 = 259 = 10 mod 83
We have to find a value of n such that \(7n^{25}\) = 7 x 37 mod 83
This is equivalent to \(n^{25}\) = 37 = \(2^{20}\) mod 83
By Fermat's Theorem,
\(2^{82k}\) = 1 mod 83 for all k.
So we need to choose n such that \(n^{25}\) =\(2^{82k+20}\) mod 83
This will be satisfied if k=15
Therefore \(n^{25}\) = \(2^{1250}\) mod 83
And so n = \(2^{50}\)
This gives one value.
My problem is that I don't understand the fourth line
That is how 37 = \(2^{20}\) mod 83?
So can someone please explain this?
Comments
Sort by:
Top Newest\( 2^8 \equiv 256 \equiv 249 + 7 \equiv 7 \) (mod \(83 \))
\( \Rightarrow 2^{16} \equiv 7^2 \) (mod \(83 \))
\(\Rightarrow 2^{20} \equiv 49 \cdot 16 \equiv 784 \equiv 37 \)(mod \(83 \)) – Ameya Daigavane · 1 year, 3 months ago
Log in to reply
Wow !! I didn't think of that. Thanks a LOT Sir !!! – Abc Xyz · 1 year, 3 months ago
Log in to reply
Note that 2 is a primitive root modulo 83, so that even if the remainder weren't 37, we could find another exponent (but finding the exact exponent is difficult, in general.) instead of 20 here. – Ameya Daigavane · 1 year, 3 months ago
Log in to reply