Question

Determine whether the following is true or false:13^⁸⁵² ≡ 7^⁹⁰⁸ mod 15

Answer 1

We have, (15) = (3•5) = (3)•(5) = 2•4 = 8

So, by Euler's theorem,

13 ⁽¹⁵⁾ 1 (mod 15)

So, 13 ⁸ 1 (mod 15)

So, (13⁸)¹⁰⁶ 1 (mod 15)

So, 13⁸⁴⁸ 1 (mod 15)

Again, 13 -2 (mod 15)

So, (13)⁴ (-2)⁴ 16 1 (mod 15)

So, 13⁸⁵² 13⁸⁴⁸ • 13⁴ 1 (mod 15)

And, 7 ⁽¹⁵⁾ 1 (mod 15)

So, 7⁸ 1 (mod 15)

So, (7⁸)¹¹³ 1 (mod 15)

So, 7⁹⁰⁴ 1 (mod 15)

Again, 7² 49 4 (mod 15)

So, (7²)² 7⁴ 4² 16 1 (mod 15)

So 7⁹⁰⁸ 7⁹⁰⁴ • 7⁴ 1 (mod 15)

So, we have, 13⁸⁵² 7⁹⁰⁸ (mod 15) (proved)