One to nine

Number Theory Level 5

Find the remainder when $1111^{2222}$ is divided by 19.

You can try more of my problems here .

The answer is 17.

3 solutions

A Former Brilliant Member
Feb 11, 2015

First of all note that $1111 \equiv 9 \pmod {19}$ .

Successive powers of $1111$ leave the following remainders $9,5,7,6,16,11,4,17$ and $1$ . After that (i.e. after the $9^{th}$ power) the pattern repeats .

Now, $2222 \equiv \pmod 8$ the remainder in question will be the $8^{th}$ remainder in the above list i.e. $17$ .

Note that your solution isn't a rigorous one. You cannot claim without proof that the pattern will repeat like that indefinitely. A much simpler and rigorous solution can be given using Fermat's Little Theorem to reduce the exponentiated value into calculable small ones. Since $19$ is a prime, we can use Fermat's Little Theorem to get,

$1111^{2222}\equiv 3^{4444}\equiv 3^{-2}\pmod{19}$

Now, all you have to do is find the value of $3^{-2}\pmod{19}$ , i.e., the smallest non-negative solution to the following congruence:

$9x\equiv 1\pmod{19}$

Using the Extended Euclidean Algorithm, we can find out the value. The inverse exists since $\gcd(9,19)=1$ . On solving, we'll get $x\equiv 17\pmod{19}$

Hence, the answer is $\boxed{17}$ .

Prasun Biswas - 6 years, 3 months ago

A slightly easier solution without resorting to Extended Euclidean Algorithm:

$1111^{2222} \equiv 9^{2222} \equiv 9^{2222 \bmod {18}} \equiv 9^8 \equiv 81^4 \equiv 5^4 \equiv 25^2 \equiv 6^2 \equiv -2 \equiv 17$

Pi Han Goh - 6 years, 2 months ago

Sorry for my late reply .

There's a reason that it's a pattern. It does repeat after 9 digits, and if it wouldn't have been the case wouldn't I have got the answer wrong ? Any way, you can check it out yourself :)

But still Thanks for posting your method :)

A Former Brilliant Member - 6 years, 3 months ago

By Fermat's Little Theorem, for $\gcd(a,p) = 1$ , with $p$ prime, we have $a^{p-1} \equiv 1 \pmod p$ . So the cycle (or the pattern) repeats itself at a maximum of $p-1$ . It could be smaller than $p-1$ , which is a factor of $p-1$ itself. In this case you have $p=19 \Rightarrow p-1=18 = 2\cdot 9$ .

Knowing that $a^{\frac {p-1}{2}} \equiv 1 \pmod p$ implies $a^{p-1} \equiv 1 \pmod p$ . The inverse may not be true. For example: $3^{40} \equiv 1 \pmod {41}$ but $3^{20} \equiv 1 \pmod{41}$ is simply not true.

And that's why Prasun said that your proof is not rigorous.

Note that it's better to use Euler totient function (a special case is Fermat's Little Theorem) for modular arithmetic involving exponentiation.

Pi Han Goh - 6 years, 2 months ago

Chew-Seong Cheong
Jul 24, 2016

$\begin{aligned} 1111^{2222} & \equiv (1111 \text{ mod 19})^{2222} \text{ (mod 19)} \\ & \equiv 9^{2222} \text{ (mod 19)} \\ & \equiv 9^{ \color{#3D99F6}{2222 \text{ mod } \phi(19)}} \text{ (mod 19)} & \small \color{#3D99F6}{\text{Since } \gcd (9, 19) = 1 \text{ Euler's theorem applies}} \\ & \equiv 9^{\color{#3D99F6}{2222 \text{ mod } 18}} \text{ (mod 19)} & \small \color{#3D99F6}{\text{Euler totient function } \phi(19) = 18} \\ & \equiv 9^{\color{#3D99F6}{8}} \equiv 81^4 \equiv 5^4 \text{ (mod 19)} \\ & \equiv 25^2 \equiv 6^2 \equiv 36 \text{ (mod 19)} \\ & \equiv -2 \equiv \boxed{17} \text{ (mod 19)} \end{aligned}$

Jesse Nieminen
Oct 5, 2015

${1111}^{2222} \equiv x$ (mod 19)

$1111 \equiv 9$ (mod 19) $\Rightarrow {9}^{2222} \equiv x$ (mod 19)

Fermat's Little Theorem tells us that $9^{18} \equiv 1$ (mod 19)

$2222 \equiv 8$ (mod 18) $\Rightarrow {9}^{8} \equiv x$ (mod 19)

$9^2 \equiv 5$ (mod 19)

$9^4 \equiv 5^2 \equiv 6$ (mod 19)

$9^8 \equiv 6^2 \equiv 17$ (mod 19) $\Rightarrow x = \boxed{17}$

One to nine

The answer is 17.

3 solutions

0 pending reports