Intermezzo

by t0rajir0u, Jan 6, 2007, 6:37 AM

A short demonstration.

Problem: Prove Bezout's Lemma. That is, given two integers $a, b$ such that $gcd(a, b) = d$ , there exist integers $x, y$ such that

$ax+by = d$

There are ways to do this by, say, considering the numbers $a, a+b, ...$ and so forth. But here is a really great trick:

Let $S =\{ ax+by\, | ax+by > 0,\, x, y\in\mathbb{Z}\}$ . This is a set of positive integers, so it has a minimal element. Let that element be $e$ .

Consider what happens when we divide $e$ into $a$ . The division algorithm tells us

$a = qe+r, 0\le r < e$

Recall that $e = ax+by$ for some integers $x, y$ . Then

$r = a(1-qx)-b(qy)$

If $r\neq 0$ then $r\in S$ and it has absolute value less than $e$ , but we assumed that $e$ was minimal. Hence $r = 0$ , so $e | a$ .

Symmetrically, $e | b$ , so $e | gcd(a, b) = d$ .

But of course, because $e = ax+by$ and because $d | a, b$ it follows that $d | ax+by\implies d | e$ .

$e$ and $d$ divide each other and are both positive, so $e = d$ . QED.

This is a brilliant piece of rigorous elementary number theory. Two of my favorite techniques from PROMYS, the extremal principle (the minimal element of a set of positive integers) and the division algorithm (which has surprisingly deep consequences - you'd be surprised!), conclude the proof very neatly. Not only is the proof of the lemma itself great, but it lends to a quick proof of another nice result (and probably a lot more).

(Possibly coming soon: an extended discussion of the division algorithm, which doesn't get the respect it deserves.)

Practice Problem: Show that $gcd(a^{n}-1, a^{m}-1) = a^{gcd(n, m)}-1$ .

Comment

6 Comments

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Hey, I just proved that a few days ago the same way you did. I didn't know it was called Bezout's Lemma, and I also can't find any other ways to prove it . . . -_-

by chess64, Jan 6, 2007, 2:15 PM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chess64 wrote:

I also can't find any other ways to prove it . . . -_-

The proof that seems to me to come to mind most easily and to be the most straightforward is this: Consider the special case $gcd(a, b) = 1$ . Then the sequence

$b, 2b, 3b, ... ab \bmod a$

Covers every residue class $\bmod a$ (because they must be distinct), so there exists $k$ such that

$kb \equiv 1 \bmod a$

Multiply by an arbitrary $gcd(a, b) = d$ to get the full result.

by t0rajir0u, Jan 7, 2007, 3:35 AM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

I think it should be $r = a(1-qx)-bqy$ , because you can't really assume that $q=1$ ...the proof still works tho.

For the practice problem, just note that repeatly perform euclidean algo on the stuffs, then one note that the exponent is undergoing a euclidean algo progression also, so we'll end up with the minimal element of the form $mx+ny$ , which is the gcd.

Or you can treat them as polynomials, and note that the first one has all the $m$ th roots of unity, which the second one has all the $n$ th roots of unity, so the common roots are the $\gcd(m, n)$ th roots of unity.

Isn't that from WOOT handout...???

by pkerichang, Jan 8, 2007, 4:43 AM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pkerichang wrote:

Or you can treat them as polynomials, and note that the first one has all the $m$ th roots of unity, which the second one has all the $n$ th roots of unity, so the common roots are the $\gcd(m, n)$ th roots of unity.

Isn't that from WOOT handout...???

Basically, cyclotomic polynomials? That's a great way to do it, too, but I like this proof because it's compact and doesn't use complicated results.

by t0rajir0u, Jan 12, 2007, 9:55 PM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

This can be generalized as follows:
Let R be a ring with a norm function N:R\{0}--->{0,1,2,3,...} satisfying
the following two requirements for all r,s \in R not equal to 0:
1) N(rs)>N(r)N(s) and
2) There exist t,v \in R such that r=st+v and N(r)>N(v).

Then the ideal generated by any two elements (x,y) is principal (i.e. can be expressed as the ideal generated by the single element gcd(x,y)).

Examples of nice rings R (called Euclidean domains) are the integers, the gaussian integers, and the polynomial ring over a field.

Also, Euclidean domains are also always UFDs, and modules over Euclidean domains have nice properties.

by n^4 4, Jan 16, 2007, 2:52 AM

Report

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

The polynomial Bezout theorem can be viewed as a q-analog of the integer Bezout theorem. This leads to a slick proof that yields the
integer Bezout theorem via the specialization x = 1, see
http://www.mathlinks.ro/viewtopic.php?p=1426109

by billwgd, Mar 25, 2009, 3:33 AM

Report

Submit

orz $~~~~$
by clarkculus, Jan 10, 2025, 4:13 PM
Insanely auraful
by centslordm, Jan 1, 2025, 11:17 PM
Fly High
by Siddharthmaybe, Oct 22, 2024, 8:34 PM
Dang it he is gone ( /revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive/revive.
by 799786, Aug 4, 2022, 1:56 PM
annoying precision
by centslordm, May 16, 2021, 7:34 PM
rip t0rajir0u
by OlympusHero, Dec 5, 2020, 9:29 PM
Shoutbox bump xD
by DuoDuoling0, Oct 4, 2020, 2:25 AM
dang hes gone
by OlympusHero, Jul 28, 2020, 3:52 AM
First shout in July
by smartguy888, Jul 20, 2020, 3:08 PM
https://artofproblemsolving.com/community/c2448

has more.

-πφ
by piphi, Jun 12, 2020, 8:20 PM
wait hold up 310,000
people visited this man?!?!??
by srisainandan6, May 29, 2020, 5:16 PM
first shout in 2020
by OlympusHero, Apr 4, 2020, 1:15 AM
in his latest post he says he moved to wordpress
by MelonGirl, Nov 16, 2019, 2:43 AM
Please revive!
by AopsUser101, Oct 30, 2019, 7:10 PM
first shout in october fj9odiais
by bulbasaur., Oct 14, 2019, 1:14 AM
t0rajir0u is beast dude. I bet he'll make IMO this year
by #H34N1, Mar 26, 2008, 2:37 AM
"annoying precision" is somewhat of an understatement, don't you think?
by xscapezaer, Mar 23, 2008, 10:06 PM
Wow. Just by looking at the page--I gained IQ points. That's uncanny. Keep it up!
by The_Scintillator, Mar 21, 2008, 2:20 AM
Mmm t0r... Are you a senior? You're too genius Nice Blog btw... But for the sake of some less advanced people, go about defining some terms...
by resurrection, Jan 31, 2008, 1:08 AM
weird
by Airjohn6, Jan 30, 2008, 11:52 PM
pls help me with integrals i cant private message u b/c i just joined mathlinks, write me back at memena@loyno.edu
by memena, Jan 22, 2008, 2:18 AM
Can you post more problems about number theory? I'd like to suggest you about combinatorial problems!
by ghjk, Jan 10, 2008, 7:03 AM
The article: A Digression is nice
by FOURRIER, Nov 5, 2007, 4:47 PM
Interested in number theory? Mmm... I am bad in number theory but I need to take it. Hope that you can help me.
by ifai, Oct 13, 2007, 7:14 AM
your blog is very useful and i like it.
by lovejrz, Oct 12, 2007, 9:26 AM
madness
by madness, Oct 4, 2007, 4:48 PM
t0r, I recommend you watch out at the RSI-PROMYS frisbee game this weekend. You betrayed both MOP and PROMYS for RSI. I'm not going to be there, but let's just say there's a hitman after you.
by K81o7, Jul 27, 2007, 3:27 AM
hello.
by ajai, Jul 13, 2007, 12:52 AM
just drop by to say hello! and digging for stuffs that I could understand
by jeez123, Jun 30, 2007, 5:02 PM

128 shouts

Annoying precision

Intermezzo

by t0rajir0u, Jan 6, 2007, 6:37 AM

6 Comments