# To prove an elementary statement

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.

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

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.

• Thanks a lot Mixed math for spending time answering. +1 – IDOK 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}$.

• 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 ?. – IDOK 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 – IDOK 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).

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