a^n | b^n => a|b: I'm having trouble finishing up the proof

[Steven G]

I am having trouble finishing up the proof for a^n | b^n => a|b. If I was a student I would think about this for days but 4-5 hours is long enough these days. A hint would be nice.
Here is what I have so far.

Proof: Let d = gcd(a,b) implies d|a and d|b implies a=rd and b=sd, where gcd(r,s)=1
[note: if r=1 then a=d implies b=sa implies a|b----so it suffices to show that r=1]
Given a^n | b^n which implies b^n = m*a^n
Define d'= gcd(a^n, b^n)
By previous theorem, gcd(r,s) = 1 implies gcd(r^n, s^n) = 1

There exist x and y in Z, s/t d=ax+by
There exist x' and y' in Z s/t d' = x'a^n + y'b^n
There exist x" and y" in Z s/t 1 = x"r^n + y"s^n
There exists x''' and y''' in Z s/t 1 = rx''' + sy'''
...???

 

[blamocur]

Not the most elegant approach, but I'd look at prime factorizations of 'a' and 'b'.

 

[Steven G]

Not the most elegant approach, but I'd look at prime factorizations of 'a' and 'b'.

Yes, I can easily prove it that way. However the book that I am studying number theory from hasn't gotten into prime factorization yet. The author clearly wants me to use the definition of a|b.

 

[blamocur]

Another approach could be reducing the problem to the case of mutually prime 'a' and 'b'.

 

[lev888]

I am having trouble finishing up the proof for a^n | b^n => a|b. If I was a student I would think about this for days but 4-5 hours is long enough these days. A hint would be nice.
Here is what I have so far.

Proof: Let d = gcd(a,b) implies d|a and d|b implies a=rd and b=sd, where gcd(r,s)=1
[note: if r=1 then a=d implies b=sa implies a|b----so it suffices to show that r=1]
Given a^n | b^n which implies b^n = m*a^n
Define d'= gcd(a^n, b^n)
By previous theorem, gcd(r,s) = 1 implies gcd(r^n, s^n) = 1

There exist x and y in Z, s/t d=ax+by
There exist x' and y' in Z s/t d' = x'a^n + y'b^n
There exist x" and y" in Z s/t 1 = x"r^n + y"s^n
There exists x''' and y''' in Z s/t 1 = rx''' + sy'''
...???

How about a proof by induction? Tried it, can't quite wrap my mind around the logic of the induction step yet...
I asked ChatGPT, it gave me a proof, but I am not 100% sure it's correct.

 

[topsquark]

I don't know if it would be any faster, but my first thought was proof by contradiction.

-Dan

 

[lookagain]

I am having trouble finishing up the proof for a^n | b^n => a|b.

Would an alternate method of using the contrapositive help? I have not done it myself.

Contrapositive statement:

If a does not divide b, then \(\displaystyle \ a^n \ \) does not divide \(\displaystyle \ b^n.\)

 

[Steven G]

The author of the textbook which the problem came from gave the hint to show that r=1.

 

[blamocur]

The author of the textbook which the problem came from gave the hint to show that r=1.

[imath]r,s[/imath] are mutually prime, thus [imath]\exists f,g : fs+gr = 1 \rightarrow fs = (1-gr)[/imath]
But [imath]r^n | s^n \rightarrow r^n | f^n s^n = (1-gr)^n[/imath]
Does this look good enough ?

 

[Steven G]

[imath]r,s[/imath] are mutually prime, thus [imath]\exists f,g : fs+gr = 1 \rightarrow fs = (1-gr)[/imath]
But [imath]r^n | s^n \rightarrow r^n | f^n s^n = (1-gr)^n[/imath]
Does this look good enough ?

What you wrote is valid, but I still don't see why r=1 (or a|b)

 

[blamocur]

What you wrote is valid, but I still don't see why r=1 (or a|b)

[imath]r^n | (1-gr)^n \rightarrow (1-gr)^n = p r^n = p_2 r[/imath]
But [imath]1-gr)^n = 1 + p_3 r[/imath] thus we get [imath]1+p_3r = p_2 r \rightarrow (p_2-p_3)r = 1[/imath], which means that [imath]r[/imath] divides 1.

 

[Steven G]

Wait a minute. I have a problem with your post #9.
If r and s are mutually prime, then how can rⁿ | sⁿ? If rⁿ | sⁿ is true, by symmetry, wouldn't sⁿ | rⁿ as well? Then rⁿ and sⁿ would just differ by maybe a sign.
What am I missing??


Clearly, gcd(4,9)=1. 4|9, no! 4ⁿ | 9ⁿ, no!

 

[blamocur]

If r and s are mutually prime, then how can rn | sn?

'r' and 's' are mutually prime because they came from dividing 'a' and 'b' by their GCD, i.e. gcd(r,s) = 1.
[imath]r^n | s^n[/imath] because [imath]a^n | b^n[/imath]

If rn | sn is true, by symmetry, wouldn't sn | rn as well?

Division is not symmetric.

 

[Steven G]

'r' and 's' are mutually prime because they came from dividing 'a' and 'b' by their GCD, i.e. gcd(r,s) = 1.
[imath]r^n | s^n[/imath] because [imath]a^n | b^n[/imath]

Division is not symmetric.

How did I not see that [imath]r^n | s^n[/imath] because [imath]a^n | b^n[/imath]?
I know that division is not symmetric. I was thinking that if randomly [imath]r^n | s^n[/imath], then naturally [imath]s^n | r^n[/imath]

 

[Steven G]

Here is my proof:

Fact: If aⁿ | bⁿ, then a|b
Proof: Let d=gcd(a,b) => a=rd and b =sd, where gcd(r,s) = 1 => there exists u and v in Z s/t 1=ru+sv =>sv = 1 - ru.
Now aⁿ | bⁿ iff (rd)ⁿ | (sd)ⁿ iff rⁿ | sⁿ iff rⁿ | sⁿvⁿ iff rⁿ | (1-ru)ⁿ =>(1-ru)ⁿ = prⁿ=(pr^n-1)r = p₂r.
(1-ru)ⁿ= 1+p₃r. Then p₂r= 1+p₃r => (p₂-p₃)r = 1 =>r|1 => r=1 =>a=d=>b=sa => a|b

 

[Steven G]

I'm not sure why the above proof was so hard for me given that I was able to do many other proofs of this type of equal difficulty.
Having said that, I do think that proofs like this, imo, are more elegant than using prime factorization.