Associated Topics || Dr. Math Home || Search Dr. Math

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

```

```
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/
```
Associated Topics:
High School Discrete Mathematics
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search