2
$\begingroup$

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.

  • 0
    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$).2012-07-07

5 Answers 5

10

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

8

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.

  • 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.2012-07-07
6

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

  • 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.2012-07-10
4

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

3

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$