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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have an elementary doubt, Sorry for disturbing you all. I have a statement of this sort. $$r^2-1=p^a(f(p))=(r+1)(r-1). \tag{1}$$ Where $r$ is an even number, and $p$ is an odd prime. $f(p)$ is a degree $n$ polynomial in $p$ with integer coefficients ( Courtesy : André Nicolas ) , $a \in \mathbb{Z}$ is a variable $>0$.

Now from the statement $(1)$ can we infer that $p^a \mid (r+1)(r-1)$ ?.

If so, $p$ being a prime, can't divide both of them (from Euclid's theorem ) . So $p^a$ divides either $(r+1)$ or $(r-1)$.

So then can we conclude that $r=kp^a \pm 1 $ for some $k>0 $?.

I told the same thing with some professor, and he is saying that it is false, and we can't write $$[\ r^2-1=p^a(f(p))=(r+1)(r-1) \ ]\implies r=kp^a \pm 1.$$ He gave me a counter example , which is $8\cdot6=48=2^4\cdot3$. He is now saying that my statement is like saying either $8 \text{ or } 6 $ divides $3$ which is utterly false.

So my learned elders in this community, please judge who is correct , me or the professor ?.

In any of the case, please do provide some good explanation.

Thank you.

share|cite|improve this question
up vote 1 down vote accepted

Your statement is correct. $p^a$ divides either $r+1$ or $r-1$, so either there exists $k>0$ such that $kp^a = r+1 \Rightarrow r = k p^a-1$, or else there exists $k$ such that $kp^a=r-1 \Rightarrow kp^a+1$.

The "counterexample" given is not applied properly. Here $r=7$ and $p^a$ should be a power of an odd prime that divides $48$. In this case $3^1$ is the only choice, and your claim is that $7=k3^1\pm 1$ for some $k>0$, which is clearly satisfied by $k=2$.

share|cite|improve this answer
Thanks a lot zander for your perfect example. +1 – Iyengar Jul 1 '12 at 15:56

Allow me first to distil the question. We have that $p^a|(r-1)$ or $p^a|(r+1)$, and you want to know if that means that $r = kp^a \pm 1$.

That implication is false in general. The great assumption that you're using is that $\gcd (r+1,r-1) = 1$. But it is possible for $2$ to divide both. This is the key behind your professor's counterexample, as $(6,8)=2$. But if you happen to know that $p \neq 2$, then your desired statement is true.

In fact, I only just now reread to see that you require $p$ to be an odd prime. And in that case, your statement is correct.

share|cite|improve this answer
Thanks a lot Mixed math for spending time answering. +1 – Iyengar Jul 1 '12 at 15:57

If $r^2-1\equiv 0 \pmod{p^a}$, where $a \ge 1$ and $p$ is an odd prime, then $r\equiv 1 \pmod{p^a}$ or $r\equiv -1\pmod{p^a}$. This implies that $r=kp^a+1$ for $r=kp^a-1$ for some integer $k$. Your argument for this is perfectly correct.

Remark: Of course the argument (and result) break down for the prime $2$. But a modified version of the result holds. We can at least say that $r=k2^{a-1}+1$ or $r=k2^{a-1}-1$ for some integer $k$. This is because one of $r-1$ or $r+1$ is congruent to $2$ modulo $4$, so the other must be divisible by $2^{a-1}$.

share|cite|improve this answer
Thanks a lot sir, +1. Sir suppose , we are given only this statement. $[\ r^2-1=p^a(f(p))=(r+1)(r-1) \ ]\implies r=kp^a \pm 1.$ So can we say that $p^a | (r+1)(r-1) $ ? from that statement ?. – Iyengar Jul 1 '12 at 15:56
The part $r^2-1=p^af(p)$ already almost says it. We do need to specify that $f(p)$ is an integer. This happens if, for example, the polynomial $f$ has integer coefficients. You did not explicitly specify that, and should. – André Nicolas Jul 1 '12 at 16:01
Yes sir. Thank you, there $f(P)$ is an integer, I now fix it, thank you. @AndréNicolas – Iyengar Jul 1 '12 at 16:04

It is true. Hint: $\rm\:p\nmid B\!-\!C,\,\ p^n\:|\:BC\:\Rightarrow\:p^n\:|\:B\:$ or $\rm\:p^n\:|\:C\,\ $ (else $\rm\:p\:|\:B,C\:\Rightarrow\:p\:|\:B\!-\!C\,)$

Even more generally if $\rm\:(A,B,C)=1\:$ then $\rm\:A\:|\:BC\:\Rightarrow\:A = bc,\, b\:|\:B,\,c\:|\:C,\,(b,c) = 1.\:$ Indeed, since $\rm\:A,B,C\:$ have no common factor, if $\rm\:p^n\:|\:A\:$ then $\rm\:p^n\:|\:B\:$ or $\rm\:p^n\:|\:C,\:$ else $\rm\:p\:|\:A,B,C,\:$ contra hypothesis. Thus the primes dividing $\rm\:A\:$ split disjointly into $\rm\:B\:$ and $\rm\:C.\:$

You special case is $\rm\:(A,B\!-\!C) =1\:$ (e.g. $\rm\:A\:$ odd, $\rm\:B\!-\!C = 2^k),\:$ hence $\rm\:(A,B,C) = 1\:$ (else $\rm\:p\:|\:A,B,C\:\Rightarrow\:p\:|\:A,\,B\!-\!C).\:$ In particular, if $\rm\:A\:$ is a prime power then $\rm\:A\:|\:B\:$ or $\rm\:A\:|\:C.$

Remark $\ $ Generally $\rm\:A\:|\:BC\:\Rightarrow\: A = (A,B)\,(A,C)\:$ when $\rm\:(A,B,C)=1.\:$ This allows us to split $\rm\:A\:$ given a splitting of a multple of $\rm\:A\:$ that is $\rm\:A$-nontrivial, i.e. $\rm\:A\nmid B,C.\:$ This is how some factorization algorithms work. See here for more on this refinement based view of factorization (Riesz interpolation, Schreier refinement, Euler's four number theorem (Vierzahlensatz), etc).

share|cite|improve this answer
Thanks a lot sir, for spending time. +1. Good answer. – Iyengar Jul 1 '12 at 17:23
Good reference sir.. But if you are interested in diophantine equations can you help me with this ?. – Iyengar Jul 1 '12 at 17:45

Your Answer


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.