1
$\begingroup$

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

Similar questions — 713064, If $\gcd(a,b)=1$, then $\gcd(a+b,a^2 -ab+b^2)=1$ or $3$., calculate the gcd of $a+b$ and $p^4$, Values of $\gcd(a-b,\frac{a^p-b^p}{a-b} )$

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

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dwayne E. Pouiller Jan 5 '14 at 14:39
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks, but I don't grasp your answer. Can you please amplify your seocnd sentence in your answer and not in comments? $\endgroup$ – Dwayne E. Pouiller Apr 7 '14 at 13:50
  • $\begingroup$ @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$ $\endgroup$ – lab bhattacharjee Apr 7 '14 at 14:31
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque May 14 '14 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.