Got a question on my midterm in discrete mathematics and I can' figure out how to approach it:
$19^{3701}+1 \equiv 0\ (\textrm{mod}\ 20)$
I was thinking about Fermat´s little theorem, but the 20 is not a prime ...
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ 19 is congruent to -1 mod 20 $\endgroup$– John McGeeNov 23, 2014 at 23:28
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
$19^{3701} = (20 - 1)^{3901}$. Now the binomial expansion contains terms all of which are divisible by $20$ except for the last one, $(-1)^{3901} = -1$.
Hence
$$19^{3701}+1 \equiv -1 + 1 \equiv 0\ (\textrm{mod}\ 20)$$
$\begingroup$
$\endgroup$
Hint: $19\equiv -1\pmod{20}{}$
If you hadn't been so lucky with the number $19$, there would've been two approaches. One is the Chinese remainder theorem, which breaks it down into mod $4$ and mod $5$, which is much easier.
The other approach is called Euler's theorem, which is a generalisation of Fermat's little theorem to non-prime modulus.
