# Math Help - Number Theory

1. ## Number Theory

let n,a and b be positive integers such that ab=n^2. if (a,b)=1 prove that there exist positive integers c and d such that a=c^2 and b=d^2.

2. Originally Posted by JCIR
let n,a and b be positive integers such that ab=n^2. if (a,b)=1 prove that there exist positive integers c and d such that a=c^2 and b=d^2.
I don't know the pretty way of saying it, but lets say n is prime, then n^2 can only be broken down into n*n and thus a=b=n. Then the greatest common denominator of a and b is equal to a or b, and not 1 (if n=1, then c=1 and d=1 and then a=c^2=1 and b=c^2=1 and so it is true anyway)

So n must not be prime. Then n is composite, so it has some number of prime factors, we'll denote this number with f.

then n = $n_1 * n_2 * ... * n_f$

and so $n^2 = (n_1 * n_2 * ... * n_f)(n_1 * n_2 * ... * n_f)$

which simplifies to $n^2 = n_1^2 * n_2^2 * ... * n_f^2$

and so $a*b = n_1^2 * n_2^2 * ... * n_f^2$

Because the greatest common denominator of a and b is 1, they cannot share common factors, and thus whichever prime factors of n are elements in a, they cannot be elements in b, and therefore their adjoining value must also be in the same group, for example if n_1 is in a, then it cannot be in b, and so both n_1's must be in a. Which means that $n_1^2$ is part of a's factorization. This holds true for all f prime factors of n.

Let the elements in a be denoted with c, and the elements in b be denoted with d, then a = c^2 and c is the product of some selection from the set of prime factors of n. And b = d^2 with d being the product of the remaining prime factors of n.

ie:
let cf be the f'th factor of n in the group c, and df be the same for d
$a = n_{c1}^2 * n_{c2}^2 * ... * n_{cf}^2 = (n_{c1}*n_{c2}*...*n_{cf})^2$

and

$b = n_{d1}^2 * n_{d2}^2 * ... * n_{df}^2 = (n_{d1}*n_{d2}*...*n_{df})^2$