Results 1 to 3 of 3

Math Help - Prime Divisibility Proof

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    86

    Prime Divisibility Proof

    Let m,n be elements of the Natural numbers. Prove that if m divides n and p is a prime factor of n that is not a prime factor of m, then m divides n/p

    The following facts can be used:

    *Every integer >= 2 can be factored into primes.

    *Let m,n be in the Integers:
    - gcd(m, n) divides both m and n
    - unless m and n are both 0, gcd(m, n) > 0
    - every integer that divides both m and n also divides gcd(m, n)

    *For all k,m,n that are elements of the Integers,
    -gcd(km, kn) = |k|gcd(m, n)

    *Let p be prime and m,n be elements of the Natural numbers. If p|mn then p|m or p|n
    (Euclid's Lemma)

    *Every integer >= 2 can be factored uniquely into primes.

    Some insight into this problem would be really beneficial, thanks a lot!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1
    Quote Originally Posted by jstarks44444 View Post
    Let m,n be elements of the Natural numbers. Prove that if m divides n and p is a prime factor of n that is not a prime factor of m, then m divides n/p

    The following facts can be used:

    *Every integer >= 2 can be factored into primes.

    *Let m,n be in the Integers:
    - gcd(m, n) divides both m and n
    - unless m and n are both 0, gcd(m, n) > 0
    - every integer that divides both m and n also divides gcd(m, n)

    *For all k,m,n that are elements of the Integers,
    -gcd(km, kn) = |k|gcd(m, n)

    *Let p be prime and m,n be elements of the Natural numbers. If p|mn then p|m or p|n
    (Euclid's Lemma)

    *Every integer >= 2 can be factored uniquely into primes.

    Some insight into this problem would be really beneficial, thanks a lot!
    Given p does not divide m and that p is prime so we conclude that gcd(p,m)=1.

    So there exist integers x and y such that:
    px + my=1.
    Multiply both sides by n/p to get nx + (n/p)m=n/p.
    Observe that m divides LHS so m divides RHS hence m divides n/p
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by jstarks44444 View Post
    Let m,n be elements of the Natural numbers. Prove that if m divides n and p is a prime factor of n that is not a prime factor of m, then m divides n/p

    The following facts can be used:

    *Every integer >= 2 can be factored into primes.

    *Let m,n be in the Integers:
    - gcd(m, n) divides both m and n
    - unless m and n are both 0, gcd(m, n) > 0
    - every integer that divides both m and n also divides gcd(m, n)

    *For all k,m,n that are elements of the Integers,
    -gcd(km, kn) = |k|gcd(m, n)

    *Let p be prime and m,n be elements of the Natural numbers. If p|mn then p|m or p|n
    (Euclid's Lemma)

    *Every integer >= 2 can be factored uniquely into primes.

    Some insight into this problem would be really beneficial, thanks a lot!


    Let q be any prime that divides m , so that \displaystyle{q\nmid p\mbox{ but }q\mid m\mid n=p\cdot\frac{n}{p}\Longrightarrow q\mid\frac{n}{p}} , and

    this is true for any prime dividing m , thus...

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 27th 2010, 01:45 PM
  2. Divisibility by prime
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: April 16th 2010, 10:57 AM
  3. Prime Numbers and Divisibility
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2009, 01:21 PM
  4. Prime Numbers and Divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 10th 2009, 01:36 PM
  5. Some Prime Number Divisibility Questions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 09:17 PM

Search Tags


/mathhelpforum @mathhelpforum