# Do Question's Given GCD Statements Imply these New GCD Statements?

Are the following statements true or false, where $a$ and $b$ are positive integers and $p$ is prime? In each case, give a proof or a counterexample:

(b) If $\gcd(a,p^2)=p$ and $\gcd(b,p^2)=p^2$, then $\gcd(ab,p^4)=p^3$.
(d) If $\gcd(a,p^2)=p$ then $\gcd(a+p,p^2)=p$.

(b) No: take $a=p$ and $b=p^3$.
(d) No: take $a=p=2$.

(b) $\gcd(\color{brown}{a}, \color{seagreen}{p^2}) = p \implies p|a \implies \color{brown}{pk_1=a}$ for some integer $k_1$. $\; p|\color{seagreen}{p^2}$ is always true — forget it.

$\gcd(\color{brown}{b}, \color{seagreen}{p^2}) = p^2 \implies p^2|b \implies \color{brown}{p^2k_2=b}$ for some integer $k_2$. $\; p^2|\color{seagreen}{p^2}$ is always true — forget it.

(1) Thence $\gcd(\color{brown}{ab},p^4) = \gcd(\color{brown}{pk_1 \cdot p^2k_2}, p^4)$. Now what?

(d) Exactly like part (b), $\gcd(\color{brown}{a}, \color{seagreen}{p^2}) = p$ is postulated. $\gcd(a+p,p^2) = p$ is postulated, but $\gcd(a+p,p^2) = p \iff p|(a + p)$.

(2) Thence $\gcd(\color{brown}{a}+p,p^2) = \gcd(\color{brown}{pk_1} + p, p^2)$ Now what?

(3) In Bill Dubuque's answer, why $\color{blue}{p\nmid \bar a}$?

Origin — Elementary Number Theory — Jones — p24 — Exercise 2.3

• To summarize the exact answer below: You forgot to include the "greatest" in "greatest common divisor" in your considerations. – LutzL Jan 4 '14 at 10:51

Here is one way to analyze the claims.

$\begin{eqnarray}{\rm Note}\ \ (a,p^2)=p\ \, &\iff& \color{#c00}{a=p\bar a},\,\ \color{blue}{p\nmid \bar a}\\ (b,p^2)=p^2 &\iff& \color{#0a0}{b = p^2\bar b}\end{eqnarray}$

Thus $\ (\color{#c00}a\color{#0a0}b,p^4) = (\color{#c00}{p\bar a}\,\color{#0a0}{p^2\bar b},\,p^4) = p^3(\bar a\bar b,\,p)\ [\,= p^3 \iff p\nmid \bar a\bar b\!\overset{\color{blue}{\ \ p\,\nmid\, \bar a}}\iff p\nmid \bar b\,]$

and $\,(\color{#c00}a\!+\!p,p^2) = (\color{#c00}{p\bar a}\!+\!p,p^2) = p(\bar a\!+\!1,p)\ [\, = p \iff p\nmid \bar a\!+\!1\,]$

Thus both are falsified by choosing any $\,\bar a,\bar b\,$ such that $\ p\mid \bar a\!+\!1,\, \bar b$

• Thanks. Upvote. Can you please look at my sequel in my original? I just want to make certain some steps. Can you please write back in your answer? I have bad eyes — comments are too small. – Dwayne E. Pouiller Jan 5 '14 at 14:39

As $p$ is prime,

if the highest power of $p$ that divides $a$ is $A$ then min$(A,2)=1\implies A=1$

so, $(a,p^2)=p\implies$ the highest power of $p$ that divides $a$ is $1$

and similarly, $(b,p^2)=p^2\implies$ the smallest power of $p$ that divides $b$ is $2$

Check with $b=p^3c$ where $c$ is some integer

• @DwayneE.Pouiller, gcd contains the common highest power of any prime, right? If the highest power of $p$ in $a$ is $A$ and we know the highest power of $p$ in $p^2$. So, the power of $p$ contained in GCD will be min$(2,A)$ But as it is $p=p^1$ min$(2,A)=1$ – lab bhattacharjee Apr 7 '14 at 14:31

I amplify Bill Dubuque's answer which works backwards from the question's claims that (b) $\gcd(ab,p^4)=p^3$ and for (d) $\gcd(a+p,p^2)=p$.

$\begin{eqnarray}{\rm Note}\ \ (a,p^2)=p\ \, &\iff& \color{#c00}{a=p\bar a},\,\ \color{blue}{p\nmid \bar a}\\ (b,p^2)=p^2 &\iff& \color{#0a0}{b = p^2\bar b}\end{eqnarray}$

Thus $\ (\color{#c00}a\color{#0a0}b,p^4) = (\color{#c00}{p\bar a}\,\color{#0a0}{p^2\bar b},\,p^4) = p^3(\bar a\bar b,\,p)\$

(b) The question's querying if this $\,= p^3$. Work backwards. $p^3\gcd(\bar a\bar b,\,p)\ = p^3 \iff$ Divide by $p^3$ $\iff \gcd(\bar a\bar b,\,p) = 1 \iff p\nmid \bar a\bar b \iff p\nmid \bar a\bar b\!\overset{\color{blue}{\ \ p\,\nmid\, \bar a}}\iff p\nmid \bar b\,$

(d) and $\,(\color{#c00}a\!+\!p,p^2) = (\color{#c00}{p\bar a}\!+\!p,p^2) = p(\bar a\!+\!1,p)\$

Question's querying if this $= p$. Work backwards. $p(\bar a\!+\!1,p)\ = p \iff$
Divide by $p \iff \gcd(\bar a+1,p)= 1 \iff p \nmid \bar a+1$

Thus both are falsified by choosing any $\,\bar a,\bar b\,$ such that $\ p\mid \bar a\!+\!1,\, \bar b$

• Yes, it appears that you do correctly comprehend the cited answer. I wouldn't call the method "working backwards". Rather, I simplify apply the hypotheses to reduce the claims to a simpler form. – Bill Dubuque May 14 '14 at 20:09