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.
No comments:
Post a Comment