Help with a modern algebra proof

T

trickslapper

Junior Member
Joined
Sep 17, 2010
Messages
62
Let gcd(a,b)=1. prove that gcd(a,b^n) =1 for all positive integers n.


Not sure on how to approach this, can someone give me some advice?
 
Depends on what you're familiar with.

edit: I did a^n,b. Same thing.

If you write a and b as a product of primes, it is obvious that if a and b share no common factors a^n and b wont either, since a^n just has n times as many copies as the same prime factors of a.

Another way, write ax+by=1, then a^2x^2 = 1-2by+b^2y^2, so that a^2x^2 + b(2y-by^2) = 1 (there's a proof by induction sitting in there).

There are likely other ways to do this as well.
 
I don't think induction is our professor wants us to do this one. I think we only have to use the definition of gcd(a,b)=1. So i have been playing with this and trying to show that 1=ax+b[sup:eek:9f364eh]n[/sup:eek:9f364eh]y which would then prove that gcd(a,b[sup:eek:9f364eh]n[/sup:eek:9f364eh])=1 but i'm having the hardest time doing so.

Does anyone think i could use euclids lemma for this proof? I saw some proofs that proved gcd(a[sup:eek:9f364eh]2[/sup:eek:9f364eh],b[sup:eek:9f364eh]2[/sup:eek:9f364eh])=1 and it seemed like they used euclids lemma.
 
You don't need induction, you're right. If you write ax+by=1 and expand (1-ax)^n it immediately gives you the result you're looking for.

I'm not sure how "Euclid's lemma" might work here. But the easiest proof is the first I gave. IF you've seen the fundamental theorem of arithmetic and proved: n|m if and only if all prime factors in n are also in m.
 
\(\displaystyle (x+y)^n = \sum_{i=0}^n {n \choose i}x^{n-i}y^{i}\)

y will divide all terms but the first, x all terms but the last. Think of this as a generalization of:

(x+y)^0 = 1
(x+y)^1 = x+y
(x+y)^2 = x^2 + 2xy + y^2
(x+y)^3 = x^3+3x^2y + 3xy^2 + y^3
...

As an aside, Note the coefficients are the entries in Pascal's triangle.
1
11
121
1331
...
 
when i try to expand it using that formula i get that b[sup:2j0crhlx]n[/sup:2j0crhlx]y[sup:2j0crhlx]n[/sup:2j0crhlx] * (ax)[sup:2j0crhlx]n-k[/sup:2j0crhlx]* n!/(n-k)!k!. I guess my question is, what would K be so that i can write 1=b[sup:2j0crhlx]n[/sup:2j0crhlx]y[sup:2j0crhlx]n[/sup:2j0crhlx] + aK so that i can then say that (a,b[sup:2j0crhlx]n[/sup:2j0crhlx])=1?
 
When you expand it, you will have n+1 terms, not just one. Each of them except the first is divisible by a. (the first term is 1) We don't really care about the "n choose i" part, and hence it is not worth time expanding into factorials, etc. That is (by)^n = (1-ax)^n = 1 - a*(stuff)
 
You must log in or register to reply here.
Top