# Some Prime Number Divisibility Questions

Printable View

• Feb 19th 2009, 07:38 PM
Aryth
Some Prime Number Divisibility Questions
I was given this question in class and was never given an answer:

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

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

Is it sufficient to say that:

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

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

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

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

Then again, I have no clue what I'm doing.
• Feb 19th 2009, 09:17 PM
ThePerfectHacker
Quote:

Originally Posted by Aryth
I was given this question in class and was never given an answer:

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

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

Is it sufficient to say that:

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

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

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

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

Then again, I have no clue what I'm doing.

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