0
$\begingroup$

Given a integer $n$, determine the remainder of dividing $n^n$ for 5 in terms of an adequate congruence for n.

So I'm really stuck in this exercise.

By Euler little theorem I know $n^4 \equiv 1 \mod5$ if $(n,5)=1$

Then, I'll be inclined to use somthing like $n = 4k + r, 0 \leq r \leq 3$

the problem is how do I determine the $n$s that actually are $(n,5)=1$ and those who are not...

$\endgroup$
5
  • $\begingroup$ You know that in the base, you have a period of $5$. In the exponent, the remainder modulo $4$ is the important thing. So what about combining these two and consider $n$ modulo ...? $\endgroup$
    – Daniel Fischer
    Feb 18, 2014 at 19:53
  • $\begingroup$ 20? I tried, But didn't help me to find nothing of interest $\endgroup$
    – FranckN
    Feb 18, 2014 at 19:56
  • $\begingroup$ You need to check based on $n\pmod 4$ and $n\pmod 5$, which is equivalent to $n\pmod {20}$. $n\equiv 1\pmod 5$ and $n\equiv 0\pmod 5$ are obvious... $\endgroup$
    – Thomas Andrews
    Feb 18, 2014 at 19:57
  • $\begingroup$ @ThomasAndrews for all the possible remainders? $\endgroup$
    – FranckN
    Feb 18, 2014 at 19:58
  • 1
    $\begingroup$ Some of them are more obvious than others, but yes. @FranckN $\endgroup$
    – Thomas Andrews
    Feb 18, 2014 at 20:01

1 Answer 1

Reset to default
3
$\begingroup$

Note that if $5|n$ then the answer is $0$

If $n\equiv 1 \mod 5$ then the remainder will always be $1$

If $n\equiv -1 \mod 5$ then the remainder will be $1$ or $4$ dependent on whether $n$ is even or odd (note: $-1$ has order $2$ in the multiplicative group of non-zero residues, and the answer therefore depends on $n \mod 2$).

If $n\equiv 2,3 \mod 5$ - these being primitive roots - you have four cases for each depending on the residue class of $n \mod 4$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .