×

# I Don't Get It!

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?

Note by Abc Xyz
8 months, 4 weeks ago

Sort by:

$$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$$) · 8 months, 3 weeks ago

Wow !! I didn't think of that. Thanks a LOT Sir !!! · 8 months, 3 weeks ago