Number Theory Proofs

Date: 06/24/99 at 21:26:35
From: Ki
Subject: Number theory

The following two questions are from _An Introduction to The Theory of 
Numbers_ by Ivan Niven and H.S. Zuckerman.

Let b and g > 0 be given integers. Prove that the equations (x,y) = g 
and xy = b can be solved simultaneously if and only if g^2|b. I'm not 
sure what the question is asking me to do. Doesn't the b have to be 
divisible by the g^2?

Also: Extend the following theorem to the set of more than two 
integers: If (a,m) = (b,m) = 1, then (ab,m) = 1.  I'm not sure how 
this theorem can be extended to three or more integers.

Thank you for your time.

Date: 06/25/99 at 08:06:05
From: Doctor Nick
Subject: Re: Number theory

Hi Ki -

This is a nice problem.

Here's how to solve it. If (x,y) = g, then g|x, and g|y, so g^2|xy.  
Thus, if (x,y) = g, and xy = b, then g^2|b. That takes care of one 
direction of the "if and only if."

Now, the other way. Suppose that g^2|b. We can write b = g^2*m for 
some integer m. Every integer can be written as a product of two 
relatively prime integers: if needed, you can always write the integer 
as the product of 1 and itself.

Say we write m as m = jk, where (j,k) = 1.
Then b = g^2*jk.
Now, let x = gj, and y = gk.
Then (x,y)=g, and xy = b.

This shows that if g^2|b, then there is a solution to the pair of 
equations (x,y) = g, xy = b.

That concludes the proof.

Your second question was: Extend the following theorem to the set of 
more than two integers: If (a,m) = (b,m) = 1, then (ab,m) = 1.

I'll give you a hint on this one. What condition do we need on g if we 
want a solution to (x1,x2,x3,...,xn) = g, (x1)(x2)(x3)...(xn) = b? Ask 
yourself: what relation does there have to be between g and b in order 
that we can find a solution?

Write back if you need more help.

Have fun,

- Doctor Nick, The Math Forum
  http://mathforum.org/dr.math/