Some Prime Number Divisibility Questions

• Feb 19th 2009, 06:38 PM
Aryth
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.
• Feb 19th 2009, 08:17 PM
ThePerfectHacker
Quote:

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