# Math Help - Prime Divisibility Proof

1. ## 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!

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

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