# 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 $\displaystyle p^n|q$ and $\displaystyle p^{n+1}\not | q$ then it is said that $\displaystyle p^n$ exactly divides q, denoted as $\displaystyle p^n || q$

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

Is it sufficient to say that:

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

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

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

$\displaystyle 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 $\displaystyle p^n|q$ and $\displaystyle p^{n+1}\not | q$ then it is said that $\displaystyle p^n$ exactly divides q, denoted as $\displaystyle p^n || q$

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

Is it sufficient to say that:

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

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

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

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

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