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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.