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 $\displaystyle p$ does not divide $\displaystyle m$ and that $\displaystyle p$ is prime so we conclude that $\displaystyle gcd(p,m)=1$.

So there exist integers $\displaystyle x$ and $\displaystyle y$ such that:
$\displaystyle px + my=1$.
Multiply both sides by $\displaystyle n/p$ to get $\displaystyle nx + (n/p)m=n/p$.
Observe that $\displaystyle m$ divides LHS so $\displaystyle m$ divides RHS hence $\displaystyle m$ divides $\displaystyle 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 $\displaystyle q$ be any prime that divides $\displaystyle m$ , so that $\displaystyle \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 $\displaystyle m$ , thus...

Tonio