Answer to Question #96789 in Combinatorics | Number Theory for Dina Patel

Question

Let a = 3333333333^7777777777 (yes, there are ten digits ”3” and ten digits ”7”). If a is
written in decimal notation, what are the last two digits?
Hint: You need to compute a mod 100. Use Euler’s theorem and the fact that φ(100) = 40.

Answer 1

Solution:

According the the Euler's theorem we

a^φ(n) $\equiv$ 1 (mod n)

It is given the $\phi$(100)= 40

a^φ(100)  $\equiv$ 1 (mod 100)

a⁴⁰ $\equiv$ 1(mod 100)

(3333333333)⁴⁰ $\equiv$ 1(mod 100) ------- (1)

Now lets apply division algorithm on 7777777777 and 40

7777777777 = 40(194444444) + 17

Hence it follows

(3333333333)^7777777777 $\equiv$ (3333333333⁴⁰) ^194444444 x (3333333333)¹⁷

$\equiv$ (1)^194444444 x (3333333333)¹⁷(mod 100)

$\equiv$ 33¹⁷

Now last two digits of

33¹ = 33

33² = 89

33⁴ = 21

33⁸ = 41

33¹⁶ = 81

So 33¹⁷ = 33¹ x 33¹⁶

$\equiv$ 33 x 81

$\equiv$ 73 is the last two digits of the 33¹⁷

Answer is 73