Welcome to our community

Be a part of something great, join today!

Number Theory Which of the following implications are right?

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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! :confused:
  • 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 :eek:

Is that what I have tried so far right? (Thinking)
 

mathbalarka

Well-known member
MHB Math Helper
Mar 22, 2013
573
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:

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,779

mathbalarka

Well-known member
MHB Math Helper
Mar 22, 2013
573
Ya, 2.
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,720
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?? :confused:

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

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,779
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?? :confused:
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?
Your method is fine.
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
Feb 15, 2012
1,967
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.