1

Let a,b be positive integers. Prove there exist positive integers $c$, $d$ such that $cd = a$ and $\gcd(c,d) = b$ if and only if $b^2\mid a$.

Proof exists $cd=a$ and $\gcd(c,d) = b \Rightarrow b^2\mid a$:

Let c = bm, d = bn. Then $cd = b^2mn = a$ and so $b^2\mid a$.

Not quite sure how to prove $b^2\mid a$ -> exists $cd=a$ and $\gcd(c,d) = b$. I thought maybe proof by contraposition. Thanks.

Michael Hardy
  • 1
miniparser
  • 1,197

1 Answers1

1

Your proof has a gap. You should take $c=bm$ and $d=bn$ with $\gcd(m,n)=1$ because then only you can ensure $\gcd(c,d)=b$.

For the other implication Since $a=b^2k$ for some $k \in \mathbb{N}$, then $a=b(bk)$. Now consider $c=b$ and $d=bk$.

Anurag A
  • 41,067