Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose $x^2\equiv x\pmod p$ where $p$ is a prime, then is it generally true that $x^2\equiv x\pmod {p^n}$ for any natural number $n$? And are they the only solutions?

share|improve this question

3 Answers 3

up vote 5 down vote accepted

No, it is not generally true. For example, $$6^2=36\equiv 6\bmod 5$$ but $$6^2=36\not\equiv 6\bmod 25.$$


Suppose we are given an integer $x$. Note that, for any prime power $p^n$, $$x^2\equiv x\pmod {p^n}\iff p^n\mid x(x-1)\iff p^n\mid x\;\; \text{ or }\;\;p^n\mid (x-1)$$ because $x$ and $x-1$ are relatively prime. Therefore, $$x^2\equiv x\pmod {p^n}$$ is true if and only if $$n\leq\max\{v_p(x),v_p(x-1)\}$$ where $v_p(d)$ denotes the number of times $p$ goes into $d$.

share|improve this answer
    
Thank you, Zev :) Is there some general rule as to when the relation is true? (There might not be, I'm just interested.) –  modulo Feb 16 '12 at 11:31
    
@modulo: No problem, glad to help - I've updated my answer with some further explanation. If there's anything I should expand on, let me know. –  Zev Chonoles Feb 16 '12 at 11:36
    
Thanks again Zev, you are most kind :) –  modulo Feb 16 '12 at 11:47
    
Your claim that $m$ will divide $x$ or $x-1$ if $m$ divides $x(x-1)$ is not true for arbitrary integers. For example, $3^2\equiv 3\pmod{6}$, $6|3(3-1)$, but $6$ does not divide either $3$ or $2$. It is true for $m$ a prime power, but false otherwise. –  Arturo Magidin Feb 16 '12 at 17:07
    
P.S. You may want to use \pmod instead of \bmod when writing congruences. \bmod is the "binary operator"; $a\bmod b$ is the the nonnegative remainder when dividing $a$ by $b$. –  Arturo Magidin Feb 16 '12 at 17:13

The English word “any” is slippery, but I think that the question asks whether if $x\equiv x^2 \pmod{p}$, then $x\equiv x^2 \pmod{p^n}$ is true for all $n$. One possible way to look at a congruence that’s true modulo all powers of a prime $p$ is that it’s really a statement about equality in the field ${\mathbb Q}_p$ of $p$-adic numbers. In particular, if $x\equiv x^2$ modulo all powers of $p$, then $x=x^2$ in ${\mathbb Q}_p$. But since the $p$-adic numbers are a field, high-school algebra tells you that either $x=0$ or $x=1$.

share|improve this answer

Way 1: Let us compute a bit. Let $p=2$. Note that $x^2\equiv x \pmod 2$ for any $x$. Is it true that always $x^2\equiv x\pmod 4$? No, let $x=2$.

Way 2: We do more work, but will get a lot more information. Rewrite the congruence $x^2\equiv x \pmod p$ as $x^2-x\equiv 0 \pmod p$, and then as $x(x-1)\equiv 0\pmod p$.

This says that the product of $x$ and $x-1$ is divisible by $p$. A product $ab$ is divisible by the prime $p$ if and only if $p$ divides $a$ or $p$ divides $b$, or both.

So $x(x-1)$ is divisible by $p$ if and only if $x$ is divisible by $p$ or $x-1$ is divisible by $p$, that is, if and only if $x\equiv 0 \pmod p$ or $x\equiv 1 \pmod p$.

Now does this force $x(x-1) \equiv 0 \pmod {p^2}$? No, for example we could take $x=p$. Certainly it is not true that $p(p-1)$ is divisible by $p^2$. We could also take $x=2p$, or $x=3p$, and so on up to $x=(p-1)p$. Or we could put the badness in the $x-1$ part, by putting $x=1+p$, or $x=1+2p$, and so on up to $x=1+(p-1)p$. We get a total of $2(p-1)$ numbers $x$ between $0$ and $p^2-1$ such that $x^2\equiv x \pmod p$ but $x^2\not\equiv x \pmod{p^2}$.

We can similarly identify the numbers $x$ between $0$ and $p^n-1$ such that $x(x-1)\equiv 0 \pmod p$ but $x(x-1)\not \equiv 0 \pmod{p^n}$. Again, they are of two types: (i) the numbers $p$, $2p$, and so on up to $p(p^{n-1}-1)$ and (ii) the numbers obtained by adding $1$ to numbers in list (i).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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