Page 1 of 2 12 LastLast
Results 1 to 15 of 16

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

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    10

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    10
    Quote Originally Posted by chiph588@ View Post
    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$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    7
    Awards
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    10
    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$
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    10
    Quote Originally Posted by chiph588@ View Post
    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$
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by dwsmith View Post
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    $\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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    10
    Quote Originally Posted by chiph588@ View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    I edited my original post.
    Your inductive hypothesis is still incomplete.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    10
    Quote Originally Posted by chiph588@ View Post
    Your inductive hypothesis is still incomplete.
    How I was able to show $\displaystyle p|a^{k+1}\mbox{?}$
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    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 $.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Jan 2009
    Posts
    715
    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 .
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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$.
    Last edited by undefined; Jun 21st 2010 at 08:11 AM.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: Oct 5th 2011, 12:45 PM
  2. Replies: 1
    Last Post: Oct 4th 2011, 02:19 AM
  3. help which one is not true
    Posted in the Geometry Forum
    Replies: 1
    Last Post: Apr 11th 2010, 10:53 PM
  4. True or False. Prove if true show counter example if false.
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: Mar 2nd 2010, 10:54 AM
  5. is that true?
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: Oct 2nd 2009, 07:00 PM

/mathhelpforum @mathhelpforum