I am trying to find the smallest positive a such that a^20 == 3 mod 101. I am kind of leaning toward there being no solutions but I don't know how to prove that. I think Fermat's Little Theorem is useful here? Any hints would be appreciated. Thanks.

Printable View

- Oct 25th 2009, 08:40 PMjimmyjimmyjimmycongruence
I am trying to find the smallest positive a such that a^20 == 3 mod 101. I am kind of leaning toward there being no solutions but I don't know how to prove that. I think Fermat's Little Theorem is useful here? Any hints would be appreciated. Thanks.

- Oct 25th 2009, 08:46 PMBruno J.
Since 101 is prime, Fermat's theorem applies and we must have $\displaystyle a^{100}\equiv 1 \mod 101$ for all $\displaystyle a$ relatively prime to $\displaystyle 101$, and 0 in all other cases. Now suppose we have an $\displaystyle a$ with $\displaystyle a^{20} \equiv 3 \mod 101$. Then

$\displaystyle (a^{20})^5 \equiv 3^5 \mod 101$

$\displaystyle a^{100} \equiv 41 \mod 101$

and that is clearly impossible.