1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 0 and 1 are also solutions. $\endgroup$ – Karolis Juodelė Oct 26 '13 at 12:32
  • $\begingroup$ 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$. $\endgroup$ – coffeemath Oct 26 '13 at 12:45
  • $\begingroup$ 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. $\endgroup$ – Y-dog Oct 27 '13 at 4:52
1
$\begingroup$

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$

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