# If $p, q$, and $r$ are relatively primes, then there exist integers $x$, $y$, and $z$ such that $px + qy + rz = 1$

True/False

If $p, q$, and $r$ are relatively primes, then there exist integers $x, y$, and $z$ such that $px + qy + rz = 1$

NOTE: $p, q$, and $r$ are positive primes.

-
Normally there are two notion of relative primality of triples: one is that no two share a nontrivial factor: $\gcd(p,q)=\gcd(q,r)=\gcd(p,r)=1$, another (weaker) condition is that there is no nontrivial factor of all three at once $\gcd(p,q,r)=1$; you would need to tell which you meant (the second condition will actually do for the problem at hand). However saying that $p$, $q$, and $r$ are primes is much stronger than even the first condition (if one ecludes equality among $p,q,r$). –  Marc van Leeuwen Jul 7 '12 at 19:18

Let's take the more general question: if $a$, $b$, and $c$ are integers and they are relatively prime, i.e., $\gcd(a,b,c)=1$, but not necessarily pairwise relatively prime, then there exist integers $x,y,z$ such that $ax+by+cz=1$.

Indeed, $\gcd(a,b,c) = \gcd(\gcd(a,b),c)$. Let $d=\gcd(a,b)$; then there exist integers $m$ and $n$ such that $am+bn=d$. And since $\gcd(d,c)=1$, there exist integers $t$ and $z$ such that $dt + cz = 1$. Now substituting the value of $d$, let $x=mt$ and $y=zn$ to get $$1 = dt + cz = (am+bn)t + cz = a(mt) + b(nt) + cz = ax + by + cz.$$

-

Unless there are some restrictions on $p, q, r$, (or $x, y, z$) the answer is yes, as we can take $z=0$ and use the well-known solution for $xp+yq=1$ where $p$ and $q$ are coprime.

-
Possibly he does not want that trivial solution. I guess the question is whether such non-zero $x,~y,~z$ exists. –  rsg Jul 7 '12 at 16:55
Yes, but following what I said, he can take any one of $x, y$ or $z$ to be anything he likes and easily get a solution for the other two. –  Old John Jul 7 '12 at 16:57

True. It holds for $p,q$, so there exist $x',y'$ such that $px'+qy'=1$. Then let $x=(r+1)x'$, $y=(r+1)y'$, $z=-1$.

In fact, this can be stated more generally: If $k>1$ and if $n_1,...,n_k\in\Bbb Z$ with any two of the $n_i$ relatively prime, then there exist $x_1,...,x_k\in\Bbb Z$ such that $$\sum_{i=1}^kn_ix_i=1.$$

-
A simple evidence is that there are planes such that 2x + 3y + 5z = 1 –  Bazinga Jul 7 '12 at 16:56
Am I right @Cameron? –  Bazinga Jul 7 '12 at 16:57
Well, that doesn't guarantee that there is some $(x,y,z)$ in the plane with $x,y,z\in\Bbb Z$. –  Cameron Buie Jul 7 '12 at 17:05
Well, since there are integers $\,x,y\,$ s.t. $\,px+qy=1\,$, such a plane will always contain the integer vector $\,(x,y,0)\,$ ...For example, $\,(-1,1,0)\,,\,(-2,0,1)\,,\,(0,-3,2)\,$ belong to the plane $\,2x+3y+5z=1\,$ –  DonAntonio Jul 7 '12 at 17:23
@Bazinga: Your point about the planes (or hyperplanes, when we're considering more than $3$ primes) is indeed a nice consequence of this. Also, if one can geometrically prove that such $(k-1)$-dimensional hyperplanes described by $$\sum_{i=1}^kn_ix_i=1$$ (with the $n_i$ as in my answer) always intersects the lattice $\Bbb Z^k=\{\langle x_1,...,x_k\rangle:x_i\in\Bbb Z\}$, then it is precisely the evidence you suggest. I'm not sure that's all that simple, though. –  Cameron Buie Jul 10 '12 at 18:55
show 2 more comments

$gcd(1,r)=1$
$\implies 1.x+rz=1$
$gcd(p,q)=1$
$\implies ps+qt=1$
So,
$(ps+qt)x+rz=1$
$\implies px^'+qy^'+rz^'=1$
As you can notice I have not used the information that $gcd(r,p)=1$ and $gcd(r,q)=1$.Hence ,it need not necessary that all the numbers should be relatively prime but any pairwise prime is sufficient i.e. $$gcd(a,b,c)=gcd(gcd(a,b),c)=gcd(1,c)=1$$

-
Hint $\$ Notice that the nonempty set $\rm\: S= \{ p\,x+ q\,y+r\,z\ :\ x,y,z\in \Bbb Z\}$ is closed under subtraction, hence a $1$-line proof shows that every element of $\rm\:S\:$ is a multiple of the least positive $\rm\: d\in S.\:$ Therefore, since $\rm\,d\,$ divides the coprime integers $\rm\,p,\,q,\,r\:$ we deduce that $\rm\:d= 1.\quad$ QED
Essentially: $\rm\: S\subset \mathbb Z\:$ subtraction-closed $\:\Rightarrow\:$ $\rm S$ mod-closed $\:\Rightarrow\:$ $\rm S\:$ gcd-closed $\:\Rightarrow\:$ $\rm\:S = gcd(S)\ \Bbb Z$