# Thread: Some Prime Number Divisibility Questions

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

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