Results 1 to 2 of 2

Thread: Some Prime Number Divisibility Questions

  1. #1
    Super Member Aryth's Avatar
    Joined
    Feb 2007
    From
    USA
    Posts
    666
    Thanks
    2
    Awards
    1

    Some Prime Number Divisibility Questions

    I was given this question in class and was never given an answer:

    Definition: If $\displaystyle p^n|q$ and $\displaystyle p^{n+1}\not | q$ then it is said that $\displaystyle p^n$ exactly divides q, denoted as $\displaystyle p^n || q$

    Question: Show that if $\displaystyle p^a || m$ and $\displaystyle p^b || n$, then $\displaystyle p^{min(a,b)} || (m + n)$

    Is it sufficient to say that:

    $\displaystyle (m,n) = p^{min(a,b)}$

    $\displaystyle (m, n+m) = p^{min(a,b)}$ since they have the same gcd.

    Since $\displaystyle p^{min(a,b)}$ is a common divisor, then

    $\displaystyle p^{min(a,b)} || (m+n)$

    Then again, I have no clue what I'm doing.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Aryth View Post
    I was given this question in class and was never given an answer:

    Definition: If $\displaystyle p^n|q$ and $\displaystyle p^{n+1}\not | q$ then it is said that $\displaystyle p^n$ exactly divides q, denoted as $\displaystyle p^n || q$

    Question: Show that if $\displaystyle p^a || m$ and $\displaystyle p^b || n$, then $\displaystyle p^{min(a,b)} || (m + n)$

    Is it sufficient to say that:

    $\displaystyle (m,n) = p^{min(a,b)}$

    $\displaystyle (m, n+m) = p^{min(a,b)}$ since they have the same gcd.

    Since $\displaystyle p^{min(a,b)}$ is a common divisor, then

    $\displaystyle p^{min(a,b)} || (m+n)$

    Then again, I have no clue what I'm doing.
    Without lose of generality say that $\displaystyle a\leq b$ this means that $\displaystyle \min(a,b)=a$. You need to show that $\displaystyle p^a || (m+n)$. Obviously, $\displaystyle p^a|(n+m)$. Now if $\displaystyle p^{a+1}|(m+n)$ we have two cases. The first case is that $\displaystyle p^{a+1}|n$, but if that happens then $\displaystyle p^{a+1}|m$ and this is a contradiction. The second case is that $\displaystyle p^{a+1} \not | n$ i.e. $\displaystyle p^a || n \implies b=a$. But in the second case it is possible that $\displaystyle p^{a+1}|(m+n)$! Here is a conterexample, $\displaystyle p=3,m=15,n=21$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: Jun 27th 2010, 12:45 PM
  2. Divisibility by prime
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Apr 16th 2010, 09:57 AM
  3. Prime Numbers and Divisibility
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 11th 2009, 12:21 PM
  4. 2 Prime Number questions
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Mar 3rd 2009, 03:24 AM
  5. prime number questions
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Nov 22nd 2008, 09:09 AM

Search Tags


/mathhelpforum @mathhelpforum