Take the 2-minute tour ×
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.

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.

share|improve this question
    
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

5 Answers 5

up vote 9 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
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
1  
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.$$

share|improve this answer
2  
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
1  
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
1  
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
1  
@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

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

share|improve this answer

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$

share|improve this answer

Your Answer

 
discard

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.