1
$\begingroup$

If gcd(p,q,r) = 1 Prove that there is an integer A such that gcd(p, q+Ar) = 1

Is the following proof good (correct)?

If we assume for the sake of contradiction that $\gcd(p,q+Ar)$ $>1\ \forall A\in \mathbb{Z}...(\text{I})$, then also (by symmetry) $\gcd(q,r+Ap)$ $>1\ \forall A\in \mathbb{Z}...(\text{II})$ and $\gcd(r,p+Cq)$ $>1\ \forall A\in \mathbb{Z}...(\text{III})$. Now since $\gcd(p,q,r)$ $=\gcd(\gcd(p,q),r)$, it will suffice to show that $\gcd(\gcd(p,q),r)$ $>1$. For the sake of brevity let $g$ $=\gcd(p,q)$, hence $p$ $=gp'$ and $q$ $=gq'$ for some relatively prime integers $p',q'$. We will assume to the contrary that $\gcd(g,r)$ $=1$, from which (Bezout) there will exist $x,y\in \mathbb{Z}$ such that $gx+ry$ $=1$, or $ry$ $=1-gx...(\alpha)$. Thus, the inequality $(\text{I})$ becomes $\gcd(gp',gq'+Ar)$ $>1\ \forall A\in \mathbb{Z}$. Setting $A$ $=A'y$ for some arbitrary integer $A'$, we get $\gcd(gp',gq'+A'ry)$ $>1\ \forall A'\in \mathbb{Z}$, or equivalently (by $(\alpha)$) $\gcd(gp',gq'+A'-A'gx)$ $>1\ \forall A'\in \mathbb{Z}$. So setting $A'$ $=p'$ yields (Euclidean Algorithm) $\gcd(gp',gq'+p')$ $>1\ \forall A'\in \mathbb{Z}$. Now, if $\gcd(g,p')$ $=1$ then the proof is complete, so it will suffice to prove this. Notice that the inequality $(\text{II})$ is equivalent to $\gcd(gq',r+q')$ $>1$. (The proof is identical to what has been done previously and the details are omitted.) There are two cases to distinguish. If $\gcd(g,q')$ $=1$, then by symmetry it will also be possible for $\gcd(g,p')$ $=1$ to hold (in some other circumstances), and the proof is complete. Otherwise, if $\gcd(g,q')$ $>1$ then it forces $\gcd(g,p')$ $=1$ to hold, and the proof is complete. Thus, in both cases the proof is complete. Q.E.D.

I am mainly unsure about the symmetry statements. The first one is explicitly mentioned in brackets ("by symmetry"); the second one arises later on in the proof. So it will be helpful to read the proof if you can, I will really appreciate it.

$\endgroup$
14
  • $\begingroup$ Your very first sentence gives an assertion that isn't immediately obvious; why is it true? $\endgroup$ – Greg Martin Nov 3 '14 at 20:54
  • $\begingroup$ @GregMartin: By symmetry $\endgroup$ – user45220 Nov 3 '14 at 20:54
  • $\begingroup$ Related: math.stackexchange.com/questions/647600 Though this question is different as it asks for a proof verification. $\endgroup$ – Bart Michels Nov 3 '14 at 20:55
  • $\begingroup$ @GregMartin: I inserted the real problem $\endgroup$ – user45220 Nov 3 '14 at 20:55
  • $\begingroup$ Taking $A=0$, $gcd(p,q) > 1$. Then certainly $gcd(p, q, r)> 1$. $\endgroup$ – gnometorule Nov 3 '14 at 20:59
1
$\begingroup$

It does not follow by symmetry from $\gcd(p,q+Ar)>1$ for all $A$ that $\gcd(q,r+Ap)>1$ and $\gcd(r,p+Cq)>1$ for all $A,C$. When you use a symmetry argument, it means that the 'symmetric' statement can be proven in an analoguous way. What you are doing here is making an assumption and then 'by symmetry', assuming another statement. So basically you are assuming too much for what the negation of "$\gcd(p,q,r)=1$" is worth.

$\endgroup$
1
  • $\begingroup$ I didn't quite understand the explanation. Can you explain some more? (The whole thing) $\endgroup$ – user45220 Nov 4 '14 at 9:34

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.