Thread: if p|a^2, then p|a. True

1. if p|a^2, then p|a. True

if $\displaystyle p|a^2$, then $\displaystyle p|a$.

This is true but how to prove it?

$\displaystyle p|a^2\rightarrow p|a*a$ now what?

2. Originally Posted by dwsmith
if $\displaystyle p|a^2$, then $\displaystyle p|a$.

This is true but how to prove it?

$\displaystyle p|a^2\rightarrow p|a*a$ now what?
For a prime $\displaystyle p, \;\; p\mid ab\implies p\mid a$ or $\displaystyle p\mid b$.

What can you conclude from this?

3. Originally Posted by chiph588@
For a prime $\displaystyle p, \quad p\mid ab\implies p\mid a$ or $\displaystyle p\mid b$.

What can you conclude from this?
Then $\displaystyle p|a \ \mbox{or} \ p|a$; therefore, $\displaystyle p|a$

4. I'm not sure I buy the theorem, unless $\displaystyle p$ is a prime. Is that a convention in number theory? If so, I would probably write out the prime factorization of $\displaystyle a$ and go from there.

5. If I wanted to generalize it, I could then say:

if $\displaystyle p|a^n$, then $\displaystyle p|a$.
$\displaystyle p|a^n\rightarrow p|a_1*a_2\dots *a_n\rightarrow p|a_1 \ \mbox{or} \ \dots \ p|a_n$ where $\displaystyle a=a_1=a_2=\dots=a_n$; hence, $\displaystyle p|a$

6. Originally Posted by dwsmith
If I wanted to generalize it, I could then say:

if $\displaystyle p|a^n$, then $\displaystyle p|a$.
$\displaystyle p|a^n\rightarrow p|a_1*a_2\dots a_n\rightarrow p|a_1 \ \mbox{or} \ \dots \ p|a_n$ where $\displaystyle a=a_1=a_2=\dots=a_n$; hence, $\displaystyle p|a$
I think induction would provide a more elegant proof.

7. Originally Posted by chiph588@
I think induction would provide a more elegant proof.
$\displaystyle P(n): \ p|a^n, \ n\geq 2$
$\displaystyle P(2): \ p|a^2\rightarrow p|a*a\rightarrow p|a \ \mbox{or} \ p|a$
$\displaystyle P(k): \ p|a^k$
$\displaystyle P(k+1): \ p|a^{k+1}$
Assume $\displaystyle P(k)$ is true.
$\displaystyle p|a^{k}$ multiple by a $\displaystyle a*p|a*a^k \rightarrow a*p|a^{k+1}\rightarrow p*(a*m)=a^{k+1}\rightarrow p|a^{k+1}\rightarrow p|a^k \ \mbox{or} \ p|a$

8. Originally Posted by dwsmith
if $\displaystyle p|a^2$, then $\displaystyle p|a$.

This is true but how to prove it?

$\displaystyle p|a^2\rightarrow p|a*a$ now what?
Consider the prime decompositions of $\displaystyle \displaystyle a$ and $\displaystyle a^2$

CB

9. Originally Posted by dwsmith
$\displaystyle P(n): \ p|a^n, \ n\geq 2$
$\displaystyle P(2): \ p|a^2\rightarrow p|a*a\rightarrow p|a \ \mbox{or} \ p|a$
$\displaystyle P(k): \ p|a^k$
$\displaystyle P(k+1): \ p|a^{k+1}$
Assume $\displaystyle P(k)$ is true.
[tex]p|a^k[\math] multiple by a $\displaystyle a*p|a*a^k \rightarrow a*p|a^{k+1}$
Having a problem since I now have a*p
We have our base case of $\displaystyle k=2$ down.

Now assume $\displaystyle p\mid a^k\implies p\mid a$ for any $\displaystyle a$

So now $\displaystyle p\mid a^{k+1}\implies p\mid a^k$ or $\displaystyle p\mid a$. Apply the inductive hypothesis are we're done.

10. Originally Posted by chiph588@
We have our base case of $\displaystyle k=2$ down.

Now assume $\displaystyle p\mid a^k\implies p\mid a$ for any $\displaystyle a$

So now $\displaystyle p\mid a^{k+1}\implies p\mid a^k$ or $\displaystyle p\mid a$. Apply the inductive hypothesis are we're done.
I edited my original post.

11. Originally Posted by dwsmith
I edited my original post.
Your inductive hypothesis is still incomplete.

12. Originally Posted by chiph588@
Your inductive hypothesis is still incomplete.
How I was able to show $\displaystyle p|a^{k+1}\mbox{?}$

13. Originally Posted by dwsmith
How I was able to show $\displaystyle p|a^{k+1}\mbox{?}$
You showed that, but that's not what you want to prove. You assume $\displaystyle p\mid a^{k+1}$ and want to conclude $\displaystyle p\mid a$.

14. Suppose $\displaystyle p|a$ is false , then one must be coprime to the other , so there exists integers $\displaystyle x,y$ such that $\displaystyle ax + py = 1$

$\displaystyle a^n x + p (a^{n-1}y) = a^{n-1}$

Let $\displaystyle a^n = pm$ because we have $\displaystyle p|a^n$

$\displaystyle pmx + pa^{n-1}y = a^{n-1}$

$\displaystyle p (mx + a^{n-1}y ) = a^{n-1}$ , we find that $\displaystyle a^{n-1}$ is the multiple of $\displaystyle p$ say $\displaystyle a^{n-1} = pm'$ , followed by $\displaystyle a^{n-1}x + p a^{n-2} y = a^{n-2}$ , $\displaystyle p(m'x + a^{n-2}y) = a^{n-2}$ so we have $\displaystyle a^{n-2} = pm'' ~ ....$ it eventually goes to $\displaystyle a = p m^{(n-1)}$ , a contradiction .

15. Nothing against simplependulum's proof, but if we write $\displaystyle a^{k+1}=a\cdot a^k$ then we can complete the induction step as was done in the original problem (first few posts of the thread).

Edit: Oh I guess the OP already did that. Well here's how I would write it then.

Induction step: Assume $\displaystyle (p | a^k \Rightarrow p | a)$.

We want to show that $\displaystyle (p | a^{k+1} \Rightarrow p | a)$.

$\displaystyle p | a^{k+1} \Leftrightarrow p | a\cdot a^k \Rightarrow (p|a \lor p|a^k) \Rightarrow p|a$. QED.

Edit 2: Sorry sorry, I've been illiterate. chiph588@ already posted basically the same thing except for the very last step. But maybe my typesetting will be easier for the OP to follow..

Edit 3 (!): By the way, it's not necessary to use base case $\displaystyle n=2$. We can use $\displaystyle n=1$ since $\displaystyle p|a^1 \Rightarrow p|a$.

Page 1 of 2 12 Last