Thread: 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!

Originally Posted by jstarks44444

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 does not divide and that is prime so we conclude that .

So there exist integers and such that:
.
Multiply both sides by to get .
Observe that divides LHS so divides RHS hence divides

Originally Posted by jstarks44444

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 be any prime that divides , so that , and

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

Tonio