1

Find the set of values for n such that $x^n \equiv{x}\mod 10$, where $n, x\in\mathbb{N}$.

This question looks like a Fermat's little theorem question but $10$ is not prime. Rather the smallest solution for n is a factor of $10, 5$. Can anyone explain or prove why this is the case? Is $5$ a unique solution for $n$?

(feel free to help put this into proper notation)

Eleven-Eleven
  • 8,806
Y-dog
  • 627
  • 0 and 1 are also solutions. – Karolis Juodelė Oct 26 '13 at 12:32
  • Do you mean: Find the set of $n$ for which $x^n \equiv x$ holds for all $x \in \mathbb{N}$. In other words $n$ is fixed and the equation should hold for all natural numbers $x$. – coffeemath Oct 26 '13 at 12:45
  • Yes n is fixed and x^n must be congruent to x in mod 10 for all x in integers (positive is sufficient). so x^n must end in the same digit x ends in for all x. – Y-dog Oct 27 '13 at 04:52

1 Answers1

1

Observe that $x^n-x=x(x^{n-1}-1)$ which is divisible by $x(x-1)$ for integer $n\ge1$

Again, $x(x-1)$ is divisible by $2\implies x^n\equiv x\pmod 2$ for $x,n\in N$

So, we need to find $x^n\equiv x\pmod 5\iff x(x^{n-1}-1)\equiv0\pmod 5 $

If $x\equiv 0\pmod 5, x^n\equiv x\pmod 5\implies x^n\equiv x\pmod {10}$

Else $x^{n-1}\equiv1\pmod 5$

Find ord$_5x$ when $x\equiv1,2,3,4$

and use the fact that ord$_px$ will divide $m$ if $x^m\equiv1\pmod p$ where $p$ is any integer relatively prime to $x$

lab bhattacharjee
  • 274,582