Don't try to cheat.

Number Theory Level 3

Find the remainder when ${ 5 }^{ 561 }$ is divided by $17$

Note - Do not use calculator.Don't cheat.

3 solutions

Jaiveer Shekhawat
Nov 17, 2014

Shivamani Patil
Oct 31, 2014

Hint: $561$ is actually a Carmichael number.

what is carmichael number

math man - 6 years, 7 months ago

Carmichael numbers satisfies the conclusion of Fermat's little theorem but they are not prime.

shivamani patil - 6 years, 7 months ago

If I remember correctly, those numbers are called pseudoprimes, aren't they?

By the way, this problem can be easily solved in two steps using the generalization of the Fermat's little Theorem,

$\begin{cases} m\equiv n \pmod{(p-1)}\\ m,n\in \mathbb{Z^+}\\ a\in \mathbb{Z}\\ p\text{ is a prime} \end{cases} \implies a^m\equiv a^n \pmod{p}$

Prasun Biswas - 6 years, 5 months ago

Utsav Playz
Feb 9, 2021

$5^2 \equiv -9 \pmod{17}$

Squaring both sides,

$5^4 \equiv -4 \pmod{17}$

Squaring both sides again,

$5^8 \equiv -1 \pmod{17}$

Raise both sides to the power of $70$ ,

$5^{560} \equiv 1 \pmod{17}$

Multiply both sides by 5,

$5^{561} \equiv 5 \pmod{17}$

Hence, the remainder when $5^{561}$ is divided by $17$ is $\boxed 5$ .