Art of Problem Solving Forum

Altheman

Let $a,b,c$ be relatively prime nonzero integers. Prove
that for any relatively prime integers $u,v,w$ satisfying
$au+bv+cw=0$ , there are integers $m,n,p$ such that
$a=nw-pv,\ b=pu-mw,\ c=mv-nu.$

**Posted:** Tue Jul 21, 2009 9:26 pm

_________________
-Alex
Altheman's Problem Column

Albanian Eagle

Bezout's theorem says that since $(w,v)=1$ then there are $n,p\in \mathbb{Z}$ so that $a=nw-pv$ .
The relation $au+bv+cw=0$ can thus be rewritten as
$bv+cw=pvu-nwu \iff (c+nu)w=(pu-b)v$
Since $(w,v)=1$ then $w|(pu-b)$ let $m=\frac{pu-b}{w}\in \mathbb{Z}$ then we have $b=pu-mw$ and $c=mv-nu$

**Posted:** Sun Jul 26, 2009 3:38 am

_________________
Gjergji Zaimi

darij grinberg

Albanian Eagle, I fear you are reading the problem wrongly: it requires $\left(u,v,w\right) = 1$ , not $\left(v,w\right) = 1$ . (The numbers should be relatively prime altogether, not pairwise relatively prime.)

Anyway, something more general holds:

Theorem 1. Let $a$ , $b$ , $c$ be three integers. Let $u$ , $v$ , $w$ be three integers such that $au + bv + cw = 0$ and such that $\mathrm{gcd}\left(u,v,w\right) = 1$ . Then, there exist three integers $A$ , $B$ , $C$ such that $a = Bw - Cv$ , $b = Cu - Aw$ and $c = Av - Bu$ .

Before we prove this, a lemma:

Lemma 2. Let $u$ , $v$ , $w$ be three integers. Then, there exist three integers $X$ , $Y$ , $Z$ such that $Xu + Yv + Zw = \mathrm{gcd}\left(u,v,w\right)$ .

Proof of Lemma 2. By Bezout's theorem (applied to the integers $u$ and $v$ ), there exist two integers $p$ and $q$ such that $pu + qv = \mathrm{gcd}\left(u,v\right)$ . By Bezout's theorem (applied to the integers $\mathrm{gcd}\left(u,v\right)$ and $w$ ), there exist two integers $s$ and $t$ such that $s\mathrm{gcd}\left(u,v\right) + tw = \mathrm{gcd}\left(\mathrm{gcd}\left(u,v\right),w\right)$ . Let $X = sp$ , $Y = sq$ and $Z = t$ . Then,

$Xu + Yv + Zw = spu + sqv + tw = s\underbrace{\left(pu + qv\right)}_{ = \mathrm{gcd}\left(u,v\right)} + tw = s\mathrm{gcd}\lef...$
$= \mathrm{gcd}\left(\mathrm{gcd}\left(u,v\right),w\right) = \mathrm{gcd}\left(u,v,w\right)$ .

Thus, Lemma 2 is proven.

Proof of Theorem 1. By Lemma 2, there exist three integers $X$ , $Y$ , $Z$ such that $Xu + Yv + Zw = \mathrm{gcd}\left(u,v,w\right)$ . Thus, $Xu + Yv + Zw = 1$ (since $\mathrm{gcd}\left(u,v,w\right) = 1$ ).

Let $A = cY - bZ$ , $B = aZ - cX$ and $C = bX - aY$ . Then,

$Bw - Cv = \left(aZ - cX\right)w - \left(bX - aY\right)v$
$= a\underbrace{\left(Xu + Yv + Zw\right)}_{ = 1} - X\underbrace{\left(au + bv + cw\right)}_{ = 0} = a\cdot 1 - X\cdot 0 = a -...$ .

In other words, $a = Bw - Cv$ . Similarly, $b = Cu - Aw$ and $c = Av - Bu$ . Thus, Theorem 1 is proven.

Theorem 1 was an assertion about $3$ -vectors and their cross product. Can anyone generalize it to $n$ -vectors and wedge products?

EDIT: As I see now, the proof of Theorem 1 comes down to applying the Lagrange formula $p\times\left(q\times r\right)=\left(p\cdot r\right)q-\left(p\cdot q\right)r$ to the three vectors $p=\left(u,v,w\right)$ , $q=\left(a,b,c\right)$ , $r=\left(X,Y,Z\right)$ in $\mathbb{R}^3$ . Generalizing the Theorem would therefore mean extending this Lagrange formula by interpreting it in terms of wedges.

darij

**Posted:** Thu Sep 24, 2009 8:59 am

_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...

mavropnevma

Darij wrote

**Posted:** Thu Sep 24, 2009 12:49 pm

_________________
Listen to REMBETIKA for decoding the handle.

darij grinberg

See also this for a similar problem.

The Lagrange formula does generalize: We have

$b\wedge \left(\ast\left(a_1\wedge a_2\wedge ...\wedge a_{n - 1}\right)\right) = \pm \sum_{j = 1}^{n - 1}\left( - 1\right)^{j ...$

for any vectors $b$ , $a_1$ , $a_2$ , ..., $a_{n - 1}$ in an $n$ -dimensional symmetric space, where I am way too lazy to figure out the $\pm$ sign. I assume this is hardly new, as it provides a duality (via the Hodge star) between two well-known chain complexes. Besides, it seems to follow from the properties of the Grassmann-Cayley algebra, but I can't find a good list of these properties (I'm mainly interested in a formula like $\left(\ast u\right)\wedge \left(\ast v\right) = \ast\left(u\vee v\right)$ , maybe with some $\pm$ sign). Any book recommendation on this?

Anyway, this doesn't seem to provide the generalization I'm seeking. That would be along the following lines:

Let $a_1$ , $a_2$ , $a_3$ , $a_4$ be four integers. Let $u_1$ , $u_2$ , $u_3$ , $u_4$ be four integers such that $a_1u_1 + a_2u_2 + a_3u_3 + a_4u_4 = 0$ and $\mathrm{gcd}\left(u_1,u_2,u_3,u_4\right) = 1$ . Do there exist eight integers $v_1$ , $v_2$ , $v_3$ , $v_4$ , $w_1$ , $w_2$ , $w_3$ , $w_4$ such that

$a_1 = \left|\begin{array}{ccc}u_2 & u_3 & u_4 \\ v_2 & v_3 & v_4 \\ w_2 & w_3 & w_4\end{array}\right|$ ;
$a_2 = \left|\begin{array}{ccc}u_3 & u_4 & u_1 \\ v_3 & v_4 & v_1 \\ w_3 & w_4 & w_1\end{array}\right|$ ;
$a_3 = \left|\begin{array}{ccc}u_4 & u_1 & u_2 \\ v_4 & v_1 & v_2 \\ w_4 & w_1 & w_2\end{array}\right|$ ;
$a_4 = \left|\begin{array}{ccc}u_1 & u_2 & u_3 \\ v_1 & v_2 & v_3 \\ w_1 & w_2 & w_3\end{array}\right|$

?

EDIT: Yes, this is true. And the corresponding generalization to $n$ variables. But this time I am using that $\mathbb{Z}$ is a principal ideal domain, while the $3$ -variables case worked for any commutative ring with $1$ .

darij

**Posted:** Thu Sep 24, 2009 1:56 pm

_________________
Now the die is cast, the first step taken, a glimmer of hope lights up our lives
Visions of the past, dreams forsaken forming right under our eyes
We are alive...