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

**dwsmith** · June 21st 2010, 06:27 AM

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

This is true but how to prove it?

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

**chiph588@** · June 21st 2010, 06:30 AM

Originally Posted by dwsmith

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

This is true but how to prove it?

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

For a prime $p, \;\; p\mid ab\implies p\mid a$ or $p\mid b$ .

What can you conclude from this?

**dwsmith** · June 21st 2010, 06:31 AM

Originally Posted by chiph588@

For a prime $p, \quad p\mid ab\implies p\mid a$ or $p\mid b$ .

What can you conclude from this?

Then $p|a \ \mbox{or} \ p|a$ ; therefore, $p|a$

**Ackbeet** · June 21st 2010, 06:33 AM

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

**dwsmith** · June 21st 2010, 06:39 AM

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

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

**chiph588@** · June 21st 2010, 06:41 AM

Originally Posted by dwsmith

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

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

I think induction would provide a more elegant proof.

**dwsmith** · June 21st 2010, 06:48 AM

Originally Posted by chiph588@

I think induction would provide a more elegant proof.

$P(n): \ p|a^n, \ n\geq 2$
$P(2): \ p|a^2\rightarrow p|a*a\rightarrow p|a \ \mbox{or} \ p|a$
$P(k): \ p|a^k$
$P(k+1): \ p|a^{k+1}$
Assume $P(k)$ is true.
$p|a^{k}$ multiple by a $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$

**CaptainBlack** · June 21st 2010, 06:50 AM

Originally Posted by dwsmith

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

This is true but how to prove it?

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

Consider the prime decompositions of $\displaystyle a$ and $a^2$

CB

**chiph588@** · June 21st 2010, 06:52 AM

Originally Posted by dwsmith

$P(n): \ p|a^n, \ n\geq 2$
$P(2): \ p|a^2\rightarrow p|a*a\rightarrow p|a \ \mbox{or} \ p|a$
$P(k): \ p|a^k$
$P(k+1): \ p|a^{k+1}$
Assume $P(k)$ is true.
[tex]p|a^k[\math] multiple by a $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 $k=2$ down.

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

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

**dwsmith** · June 21st 2010, 06:53 AM

Originally Posted by chiph588@

We have our base case of $k=2$ down.

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

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

I edited my original post.

**chiph588@** · June 21st 2010, 06:54 AM

Originally Posted by dwsmith

I edited my original post.

Your inductive hypothesis is still incomplete.

**dwsmith** · June 21st 2010, 06:57 AM

Originally Posted by chiph588@

Your inductive hypothesis is still incomplete.

How I was able to show $p|a^{k+1}\mbox{?}$

**chiph588@** · June 21st 2010, 07:06 AM

Originally Posted by dwsmith

How I was able to show $p|a^{k+1}\mbox{?}$

You showed that, but that's not what you want to prove. You assume $p\mid a^{k+1}$ and want to conclude $p\mid a$ .

**simplependulum** · June 21st 2010, 07:36 AM

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

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

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

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

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

**undefined** · June 21st 2010, 07:45 AM

Nothing against simplependulum's proof, but if we write $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 $(p | a^k \Rightarrow p | a)$ .

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

$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..