Number TheoryWhich of the following implications are right?

evinda

Well-known member
MHB Site Helper
Hi!!!
Which of the following implications are right?
• $a|b^{n} \Rightarrow a|b$
• $a^n|b^n \Rightarrow a|b$
• $a^n|b \Rightarrow a|b$
• $a^3|b^3 \Rightarrow a|b$
Prove the right ones and give a counterexample for the wrong ones.

That's what I think..
• Wrong.Counterexample: $20|10^2 \nRightarrow 20|10$
• Wrong,because $a^n|b^n \Rightarrow b^n=ka^n=(k \cdot a^{n-1}) \cdot a \Rightarrow a|b^n$,and from the first sentence it is wrong..But I have not found a counterexample!
• It is true because $a^n|b \Rightarrow b=ka^n=(k \cdot a^{n-1}) \cdot a \Rightarrow a|b$
• I think it is true,but I don't know how to prove it

Is that what I have tried so far right?

mathbalarka

Well-known member
MHB Math Helper
1. Is false, as you have shown.

2. Is true. Try assuming $b \neq 0 \pmod{a}$ and arrive at contradiction.

3. Is true. Reasoning is okay.

4. A special case of 2.

Last edited:

Staff member

MHB Math Helper
Ya, 2.

evinda

Well-known member
MHB Site Helper
1. Is false, as you have shown.

2. Is true. Try assuming $b \neq 0 \pmod{a}$ and arrive at contradiction.

3. Is true. Reasoning is okay.

4. A special case of 2.
2. Do you mean that $a \nmid b$ means that $b=q \cdot a+r (*)$
Since $a^n|b^n \Rightarrow b^n=ka^n$ ..Do I have to replace the relation (*) to show it??

3.Could I also show it in an other way?

Klaas van Aarsen

MHB Seeker
Staff member
2. Do you mean that $a \nmid b$ means that $b=q \cdot a+r (*)$
Since $a^n|b^n \Rightarrow b^n=ka^n$ ..Do I have to replace the relation (*) to show it??
I do not know what mathbalarka intended, but here's another way.

According to the Fundamental theorem of arithmetic every number has a unique prime factorization.
So suppose $a \nmid b$, then $a$ must contain a power of a prime factor that is not in $b$.
In that case $a^n$ will also have a power of a prime factor that is not in $b^n$, which is a contradiction.

3.Could I also show it in an other way?
Another way is by using the Fundamental theorem of arithmetic again.

$a^n|b$ implies that $a^n$ contains only prime powers that are also in $b$.
But then $a$ can also only contain prime powers that are also in $b$.
Therefore $a^n|b \Rightarrow a|b$.

Deveno

Well-known member
MHB Math Scholar
Yes, if $b \neq 0$ (mod $a$) this means:

$b = qa + r$ for some $0 < r < a$.

Since $a^n|b$ we have:

$b = ka^n = qa + r$.

Thus:

$ka^n - qa = r$, which is to say that:

$a(ka^{n-1} - q) = r$.

Since $a$ divides the left, $a$ divides the right, that is: $a|r$.

But $r < a$ and $r \neq 0$...how can this be?

For if $at = r$ for some integer $t$, we have:

$0 < r = at < a \implies 0 < t < 1$.

But there is no non-zero integer between 0 and 1.