# Suppose the integers $m^2$ and $n$ are relatively prime. Show that $m$ and $n^2$ are relatively prime.

My attempt so far:

Since $m^2$ and $n$ are relatively prime, $am^2 + bn = 1$ for some integers $a$ and $b$.

I know that I will have to use this to somehow prove that $cm + dn^2 = 1$ for some integers $c$ and $d$, but I'm not sure how to do this.

• Have you thought about the factorizations of $m$ and $n$ into primes? – Catalin Zara Jun 16 '16 at 2:33
• No I hadn't thought of that... but how could I do that if I don't know the values of $m$ and $n$? Would I use the Euclidean Algorithm somehow? – maths123 Jun 16 '16 at 2:37
• From the definition of primality, a prime $p$ with $p|n^2$ has $p|n$. – anomaly Jun 16 '16 at 2:50

Start with $$am^2 + bn = 1$$ and multiply by $bn$ to get $$abm^2n + b^2n^2 = bn.$$ Since $bn = 1 - am^2$ this can be written as $$abm^2 n + b^2n^2 = 1 - am^2$$ which may in turn be written as $$abm^2n + am^2 + b^2n^2 = 1.$$ Thus $$(abmn + am)m + (b^2)n^2 = 1$$ so you can take $c = abmn + am$ and $d = b^2$.

• Thanks! In an exam would I have to further prove that c and d are integers, or could I just leave it at that? – maths123 Jun 16 '16 at 2:54
• They are integers since they are basic expressions of other integers. (addition and multiplication) – Jack Tiger Lam Jun 16 '16 at 3:24

Good start. Now note that $$1=(am^2+bn)^2=(a^2m^3+2ambn)m+(b^2)n^2.$$

• Thanks! So would it be enough to say that $1 = am^2 + bn$ so $1^2 = (am^2 + bn)^2 $$\iff 1 = a^2m^4 + b^2n^2 + 2am^2bn \iff 1 = (a^2m^3 + 2abnm)m + b^2(n^2) and since (a^2m^3 + 2abnm) and b^2 are the result of addition and multiplication of integers then they will also be integers? – maths123 Jun 16 '16 at 2:51 • If you want to add anything, say that there is an integer linear combination of m and n^2 which is equal to 1, so m and n^2 are relatively prime. I think there is no need to prove that a^2m^3+2abmn and b^2 are integers. Note that I prefer the approach of Sameer Kailasa, but I wanted to complete the argument along the lines you had started. – André Nicolas Jun 16 '16 at 2:56 If p a prime divides both m and n^2, then p divides n by primality, hence p divides m^2 and n, contradicting the fact that \gcd(m^2, n) = 1. Thus, m and n^2 are relatively prime. • Thanks, I wouldn't have thought of doing it this way :) – maths123 Jun 16 '16 at 2:54 • Thanks @Sameer! This was very helpful! +1 – user345872 Jul 1 '16 at 18:43 • Haha, go Huskies! – Sameer Kailasa Jul 1 '16 at 21:01 All one-letter variables are integers. (i). If 1<u\in N then u is divisible by a prime. Proof: Let v be the least w such that 1<w\leq u and w|u. Then v is prime, for if v=w_1 w_2 with w_1>1<w_2 , then w_1 is a divisor of u with 1<w_1<w, contrary to the def'n of w. (ii). If p is prime and p|n^2 then p|n. Proof: If not then \gcd(p,m)=1 because p is prime, implying there are a,b with 1=a p+b n. But then$$n= n a p+b n^2=(n a +b (n^2/p))p$$and$n^2/p$is an integer, so$k=n a+b(n^2/p)$is an integer, and$n= k p,$so$p|n.$(iii). If$\gcd (m,n^2)> 1$then by (i), some prime$p$divides both$m$and$n^2.$But then by (ii),$p$divides$n,$so p divides both$m^2$and$n,$implying$\gcd (m^2,n)\geq p>1.\$

• What a wonderful proof, thank you :) – maths123 Jun 16 '16 at 22:10