1
$\begingroup$

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 ...

$\endgroup$
  • 1
    $\begingroup$ 19 is congruent to -1 mod 20 $\endgroup$ – John McGee Nov 23 '14 at 23:28
2
$\begingroup$

$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)$$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.