Algebraic integers
Bart Goddard
Suppose d is a squarefree integer and r and s are rational.
And suppose r+s\sqrt{d} is an algebraic integer.
Is there a (very) elementary way to argue the statement:
"Since r+s\sqrt{d} is a root of the monic polynomial
x^2-2rx+r^2-ds^2, then -2r and r^2-ds^2 must be integers."?
I don't want to appeal to a Euclidean algorithm in Z[x]
or use the phrase "minimal polynomial." This is for
elementary number theory students.
If z is an algebraic integer and we find a monic polynomial
over Q of which it is a root, how do we know the polynomial
is really over Z?
Bart
Arturo Magidin
Bart Goddard <godd...@netscape.net> wrote:
>
>Suppose d is a squarefree integer and r and s are rational.
>And suppose r+s\sqrt{d} is an algebraic integer.
>Is there a (very) elementary way to argue the statement:
>
>"Since r+s\sqrt{d} is a root of the monic polynomial
>x^2-2rx+r^2-ds^2, then -2r and r^2-ds^2 must be integers."?
>
>I don't want to appeal to a Euclidean algorithm in Z[x]
Good, since there isn't one... Perhaps you meant Q[x].
>or use the phrase "minimal polynomial." This is for
>elementary number theory students.
>If z is an algebraic integer and we find a monic polynomial
>over Q of which it is a root, how do we know the polynomial
>is really over Z?
You don't. For example, 1 is a root of x^2 - (1/2)x - (1/2), which is
certainly monic over Q but not in Z.
You would need to appeal to Gauss's Lemma or some variant
thereof. Otherwise, you don't know if perhaps r+s*sqrt(d) is a root of
some other monic polynomial with integer coefficients which is
unrelated to the one you found.
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
mag...@math.berkeley.edu
Gerry Myerson
mag...@math.berkeley.edu (Arturo Magidin) wrote:
> In article <Xns95B9ABB8F...@129.250.170.82>,
> Bart Goddard <godd...@netscape.net> wrote:
> >
> >Suppose d is a squarefree integer and r and s are rational.
> >And suppose r+s\sqrt{d} is an algebraic integer.
> >Is there a (very) elementary way to argue the statement:
> >
> >"Since r+s\sqrt{d} is a root of the monic polynomial
> >x^2-2rx+r^2-ds^2, then -2r and r^2-ds^2 must be integers."?
> >
> >I don't want to appeal to a Euclidean algorithm in Z[x]
>
> Good, since there isn't one... Perhaps you meant Q[x].
>
> >or use the phrase "minimal polynomial." This is for
> >elementary number theory students.
>
> >If z is an algebraic integer and we find a monic polynomial
> >over Q of which it is a root, how do we know the polynomial
> >is really over Z?
>
> You don't. For example, 1 is a root of x^2 - (1/2)x - (1/2), which is
> certainly monic over Q but not in Z.
>
> You would need to appeal to Gauss's Lemma or some variant
> thereof. Otherwise, you don't know if perhaps r+s*sqrt(d) is a root of
> some other monic polynomial with integer coefficients which is
> unrelated to the one you found.
For the original question, involving r + s sqrt d,
it being an algebraic integer means it satisfies x^2 + ax + b
for some integers a and b; as it also satisfies
x^2 - 2rx + r^2 - d s^2, it must satisfy their difference.
If that difference isn't identically zero, then it's constant,
which is nonsense, or it's linear, which makes r + s sqrt d
rational.
Or do you object to taking the difference as an appeal to
the Euclidean algorithm?
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
Dik T. Winter
> Suppose d is a squarefree integer and r and s are rational.
> And suppose r+s\sqrt{d} is an algebraic integer.
> Is there a (very) elementary way to argue the statement:
>
> "Since r+s\sqrt{d} is a root of the monic polynomial
> x^2-2rx+r^2-ds^2, then -2r and r^2-ds^2 must be integers."?
I do not think it is so very elementary. You need that an algebraic
integer can *not* be the root of a non-monic primitive irreducible
polynomial with coefficients in Z. If I remember right, Arturo Magidin
has posted a proof of that in this newsgroup.
> I don't want to appeal to a Euclidean algorithm in Z[x]
> or use the phrase "minimal polynomial." This is for
> elementary number theory students.
And indeed, you should not appeal to a Euclidean algorithm, as it might
not exist.
> If z is an algebraic integer and we find a monic polynomial
> over Q of which it is a root, how do we know the polynomial
> is really over Z?
You do not. For instance, 2 is a root of x^2 - (5/2).x + 1.
But that polynomial is reducible; so that is where the "irreducible"
steps in.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Dik T. Winter
> > In article <Xns95B9ABB8F...@129.250.170.82>,
> > Bart Goddard <godd...@netscape.net> wrote:
> > >
> > >Suppose d is a squarefree integer and r and s are rational.
> > >And suppose r+s\sqrt{d} is an algebraic integer.
> > >Is there a (very) elementary way to argue the statement:
> > >
> > >"Since r+s\sqrt{d} is a root of the monic polynomial
> > >x^2-2rx+r^2-ds^2, then -2r and r^2-ds^2 must be integers."?
> For the original question, involving r + s sqrt d,
> it being an algebraic integer means it satisfies x^2 + ax + b
> for some integers a and b;
I do not think that is within the knowledge of the students involved.
Gerry Myerson
wrote:
> In article <gerry-91B6EF....@sunb.ocs.mq.edu.au> Gerry Myerson
> <ge...@maths.mq.edi.ai.i2u4email> writes:
> > > In article <Xns95B9ABB8F...@129.250.170.82>,
> > > Bart Goddard <godd...@netscape.net> wrote:
> > > >
> > > >Suppose d is a squarefree integer and r and s are rational.
> > > >And suppose r+s\sqrt{d} is an algebraic integer.
> > > >Is there a (very) elementary way to argue the statement:
> > > >
> > > >"Since r+s\sqrt{d} is a root of the monic polynomial
> > > >x^2-2rx+r^2-ds^2, then -2r and r^2-ds^2 must be integers."?
> ...
> > For the original question, involving r + s sqrt d,
> > it being an algebraic integer means it satisfies x^2 + ax + b
> > for some integers a and b;
>
> I do not think that is within the knowledge of the students involved.
Then I'm understanding Bart's original question in a very different
way than you are. He said, "suppose r+s\sqrt{d} is an algebraic
integer." You can't ask a class to make that supposition if the
definition of algebraic integer is not within the knowledge of the
students. And the only definition of algebraic integer I'd expect
them to know is the one that says it's a zero of a monic polynomial
with integer coefficients.
I'm having difficulty trying to work out what your understanding
of Bart's question is. Knowing only that d is a squarefree integer
and r and s are rational will not get you from "r+s\sqrt{d} is a root of
the monic polynomial x^2-2rx+r^2-ds^2" to "2r and r^2-ds^2 must be
integers." You have to know something more about r, s, and d.
If you know their numerical values, there's no challenge in deciding
whether 2r and r^2 - d s^2 are integers or not.
Please clarify.
Timothy Murphy
>
> Suppose d is a squarefree integer and r and s are rational.
> And suppose r+s\sqrt{d} is an algebraic integer.
> Is there a (very) elementary way to argue the statement:
>
> "Since r+s\sqrt{d} is a root of the monic polynomial
> x^2-2rx+r^2-ds^2, then -2r and r^2-ds^2 must be integers."?
I would argue that r - s\sqrt(d) must also be an algebraic integer
since it satisfies the same equations over Z (or Q).
Hence so are the coefficients you give,
since they are the sum and product of these numbers.
I assume that the students know what an algebraic integer is,
or the question would be pointless.
I'd guess that they also know the algebraic integers form a ring,
since there is little point in introducing these numbers
if one doesn't prove that.
--
Timothy Murphy
e-mail (<80k only): tim /at/ birdsnest.maths.tcd.ie
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
Dik T. Winter
> In article <I8Fr0...@cwi.nl>, "Dik T. Winter" <Dik.W...@cwi.nl>
> wrote:
> > > > >Suppose d is a squarefree integer and r and s are rational.
> > > > >And suppose r+s\sqrt{d} is an algebraic integer.
> > > > >Is there a (very) elementary way to argue the statement:
> > > > >
> > > > >"Since r+s\sqrt{d} is a root of the monic polynomial
> > > > >x^2-2rx+r^2-ds^2, then -2r and r^2-ds^2 must be integers."?
> > ...
> > > For the original question, involving r + s sqrt d,
> > > it being an algebraic integer means it satisfies x^2 + ax + b
> > > for some integers a and b;
> >
> > I do not think that is within the knowledge of the students involved.
>
> Then I'm understanding Bart's original question in a very different
> way than you are. He said, "suppose r+s\sqrt{d} is an algebraic
> integer." You can't ask a class to make that supposition if the
> definition of algebraic integer is not within the knowledge of the
> students. And the only definition of algebraic integer I'd expect
> them to know is the one that says it's a zero of a monic polynomial
> with integer coefficients.
Yup, right. But how do they know that the algebraic integers involved
are the roots of a monic *quadratic* polynomial with integer
coefficients? Note that Bart wanted to avoid "minimal polynomial" for
instance.
> I'm having difficulty trying to work out what your understanding
> of Bart's question is. Knowing only that d is a squarefree integer
> and r and s are rational will not get you from "r+s\sqrt{d} is a root of
> the monic polynomial x^2-2rx+r^2-ds^2" to "2r and r^2-ds^2 must be
> integers." You have to know something more about r, s, and d.
> If you know their numerical values, there's no challenge in deciding
> whether 2r and r^2 - d s^2 are integers or not.
I think what Bart is trying to do is show for what values of r and s
"r+s\sqrt(d)" is an algebraic integer. For this purpose he creates
the quadratic. Obviously if the coefficients are integer the roots
are algebraic integers. On the other hand it is not immediately
obvious that it is also the other way around.
Bart Goddard
> But how do they know that the algebraic integers involved
> are the roots of a monic *quadratic* polynomial with integer
> coefficients?
Yeah, _quadratic_ is the issue. We have the definition of
"algebraic integer", and really nothing else. (We don't
know what a ring is, we don't know what a primitive
polynomial is, etc. These are exercises at the far end
of the exercise sets in the text book, and they are
just meant to demonstrate other integer-like systems.
Part (a) is "show that if r+s\sqrt{d} is an algebraic
integer, then it is of the form a+b\omega where a and be
are integers and \omega=<appropriate surd>.)
Bart
Will Twentyman
> Suppose d is a squarefree integer and r and s are rational.
> And suppose r+s\sqrt{d} is an algebraic integer.
> Is there a (very) elementary way to argue the statement:
>
> "Since r+s\sqrt{d} is a root of the monic polynomial
> x^2-2rx+r^2-ds^2, then -2r and r^2-ds^2 must be integers."?
>
> I don't want to appeal to a Euclidean algorithm in Z[x]
> or use the phrase "minimal polynomial." This is for
> elementary number theory students.
Let's look at a slightly different approach. r=a/b, s=e/f, a,b,e,f are
integers and b,f not 0. Also, a,b coprime, e,f coprime.
Then we are saying a/b + e*sqrt(d)/f is an algebraic integer.
x=a/b + e*sqrt(d)/f
xbf = af + be*sqrt(d)
xbf - af = be*sqrt(d)
x^2 b^2 f^2 - 2xabf^2 + a^2 f^2 = b^2 e^2 d
(b^2 f^2) x^2 + (-2abf^2) x + (a^2 f^2 - b^2 e^2 d) = 0
So: (b^2 f^2) x^2 + (-2abf^2) x + (a^2 f^2 - b^2 e^2 d) is either monic
or reducible to a constant times a monic and clearly has integer
coefficients. This means that:
x^2 + (-2a/b) x + (a^2 f^2 - b^2 e^2 d)/(b^2 f^2) is a monic polynomial
with integer coefficients. Since a and b are coprime, b = +/- 1.
Assume 1 for ease of notation.
Then x^2 + (-2a) x + (a^2 f^2 - e^2 d)/f^2 is a monic polynomial with
integer coefficients.
So: in particular, (a^2 f^2 - e^2 d)/f^2 is an integer. Since a^2 f^2
is divisible by f^2, so is e^2 d. However, d is square-free and e^2 is
coprime to f^2, since e and f are coprime. Therefor, f = +/- 1 and f^2 = 1.
So b and f are units, which means that r and s are actually integers.
Therefor, -2r and r^2-ds^2 must be integers.
I don't think I overlooked anything, but I'm sure someone will point it
out if I did.
--
Will Twentyman
email: wtwentyman at copper dot net
Dik T. Winter
But that is false in the way stated. When d is 1 mod 4, a and
b can also both be one half of an odd integer.
Dik T. Winter
...
> Let's look at a slightly different approach. r=a/b, s=e/f, a,b,e,f are
> integers and b,f not 0. Also, a,b coprime, e,f coprime.
>
> Then we are saying a/b + e*sqrt(d)/f is an algebraic integer.
>
> x=a/b + e*sqrt(d)/f
> xbf = af + be*sqrt(d)
> xbf - af = be*sqrt(d)
> x^2 b^2 f^2 - 2xabf^2 + a^2 f^2 = b^2 e^2 d
> (b^2 f^2) x^2 + (-2abf^2) x + (a^2 f^2 - b^2 e^2 d) = 0
>
> So: (b^2 f^2) x^2 + (-2abf^2) x + (a^2 f^2 - b^2 e^2 d) is either monic
> or reducible to a constant times a monic and clearly has integer
> coefficients. This means that:
>
> x^2 + (-2a/b) x + (a^2 f^2 - b^2 e^2 d)/(b^2 f^2) is a monic polynomial
> with integer coefficients. Since a and b are coprime, b = +/- 1.
> Assume 1 for ease of notation.
Or b = +/- 2...
>
> Then x^2 + (-2a) x + (a^2 f^2 - e^2 d)/f^2 is a monic polynomial with
> integer coefficients.
>
> So: in particular, (a^2 f^2 - e^2 d)/f^2 is an integer. Since a^2 f^2
> is divisible by f^2, so is e^2 d. However, d is square-free and e^2 is
> coprime to f^2, since e and f are coprime. Therefor, f = +/- 1 and f^2 = 1.
>
> So b and f are units, which means that r and s are actually integers.
> Therefor, -2r and r^2-ds^2 must be integers.
Indeed, when b = 1. It is a bit different when b = 2.
Bart Goddard
> So b and f are units, which means that r and s are actually
> integers.
But if d=-3, e.g., r and s are not integers.
Bart
Bart Goddard
> In article <Xns95BA4E408...@129.250.170.88> Bart Goddard
> <godd...@netscape.net> writes:
> > Dik T. Winter wrote:
> >
> > > But how do they know that the algebraic integers involved
> > > are the roots of a monic *quadratic* polynomial with integer
> > > coefficients?
> >
> > Yeah, _quadratic_ is the issue. We have the definition of
> > "algebraic integer", and really nothing else. (We don't
> > know what a ring is, we don't know what a primitive
> > polynomial is, etc. These are exercises at the far end
> > of the exercise sets in the text book, and they are
> > just meant to demonstrate other integer-like systems.
> > Part (a) is "show that if r+s\sqrt{d} is an algebraic
> > integer, then it is of the form a+b\omega where a and be
> > are integers and \omega=<appropriate surd>.)
>
> But that is false in the way stated. When d is 1 mod 4, a and
> b can also both be one half of an odd integer.
Not if \omega = (1+\sqrt(d))/2 in those cases.
Arturo Magidin
In article <gerry-91B6EF....@sunb.ocs.mq.edu.au>,
That's the point: how do you prove that without appeals to the minimal
polynomial?
By definition, we know that r+s*sqrt(d) satisfies ->some<- monic
polynomial with integer coefficients.
We also know it satisfies a quadratic monic polynomial with rational
coefficients.
How do you know the "some monic with integer coefficients" is
quadratic, and not of some higher degree, without appealing to
divisibility in Q[x]?
Arturo Magidin
Will Twentyman <wtwen...@read.my.sig> wrote:
>Bart Goddard wrote:
>
>> Suppose d is a squarefree integer and r and s are rational.
>> And suppose r+s\sqrt{d} is an algebraic integer.
>> Is there a (very) elementary way to argue the statement:
>>
>> "Since r+s\sqrt{d} is a root of the monic polynomial
>> x^2-2rx+r^2-ds^2, then -2r and r^2-ds^2 must be integers."?
>>
>> I don't want to appeal to a Euclidean algorithm in Z[x]
>> or use the phrase "minimal polynomial." This is for
>> elementary number theory students.
>
>Let's look at a slightly different approach. r=a/b, s=e/f, a,b,e,f are
>integers and b,f not 0. Also, a,b coprime, e,f coprime.
>
>Then we are saying a/b + e*sqrt(d)/f is an algebraic integer.
>
>x=a/b + e*sqrt(d)/f
>xbf = af + be*sqrt(d)
>xbf - af = be*sqrt(d)
>x^2 b^2 f^2 - 2xabf^2 + a^2 f^2 = b^2 e^2 d
>(b^2 f^2) x^2 + (-2abf^2) x + (a^2 f^2 - b^2 e^2 d) = 0
>
>So: (b^2 f^2) x^2 + (-2abf^2) x + (a^2 f^2 - b^2 e^2 d) is either monic
>or reducible to a constant times a monic and clearly has integer
>coefficients.
And here's the rub: you are now using implicitly using the fact that
if r is an algebraic integer, f(x) is in Z[x], and f(r)=0, then either
f is monic or else f is reducible. This is a ->consequence<- of the
fact that every f(x) in Q[x] which has f(r)=0 is a multiple of the
minimal polynomial, and that r is an algebraic integer if and only if
its ->minimal<- polynomial is monic with integer coefficients. But
those facts require the use of the Euclidean algortihm in Q[x], and do
not simply fllow from the definition of "algebraic integer" as "root
of some monic with integer coefficients".
Will Twentyman
I had a feeling there was going to be a hole like that. *sigh*
Will Twentyman
> In article <41b85...@newsfeed.slurp.net> Will Twentyman <wtwen...@read.my.sig> writes:
> ...
> > Let's look at a slightly different approach. r=a/b, s=e/f, a,b,e,f are
> > integers and b,f not 0. Also, a,b coprime, e,f coprime.
> >
> > Then we are saying a/b + e*sqrt(d)/f is an algebraic integer.
> >
> > x=a/b + e*sqrt(d)/f
> > xbf = af + be*sqrt(d)
> > xbf - af = be*sqrt(d)
> > x^2 b^2 f^2 - 2xabf^2 + a^2 f^2 = b^2 e^2 d
> > (b^2 f^2) x^2 + (-2abf^2) x + (a^2 f^2 - b^2 e^2 d) = 0
> >
> > So: (b^2 f^2) x^2 + (-2abf^2) x + (a^2 f^2 - b^2 e^2 d) is either monic
> > or reducible to a constant times a monic and clearly has integer
> > coefficients. This means that:
> >
> > x^2 + (-2a/b) x + (a^2 f^2 - b^2 e^2 d)/(b^2 f^2) is a monic polynomial
> > with integer coefficients. Since a and b are coprime, b = +/- 1.
> > Assume 1 for ease of notation.
>
> Or b = +/- 2...
Drat. Ok, if b = 2 (assume a has the appropriate corresponding sign),
then (a^2 f^2 - 4e^2d)/(4f^2) is an integer. Since a is coprime to 2,
a^2 is not divisible by 4. Therefore f^2 is divisible by 4 and f is a
multiple of 2. Suppose f=2k, k an integer.
(a^2 f^2 - 4e^2d)/(4f^2) = (4a^2 k^2 - 4e^2d)/(16k^2)
= (a^2 k^2 - e^2d)/(4k^2)
Since k^2 divides a^2 k^2, k^2 must also divide e^2d. Since f and e are
coprime, so are k and e. Therefor k^2 must divide d, which contradicts
d being squarefree. Therefor, b =/= 2.
> >
> > Then x^2 + (-2a) x + (a^2 f^2 - e^2 d)/f^2 is a monic polynomial with
> > integer coefficients.
> >
> > So: in particular, (a^2 f^2 - e^2 d)/f^2 is an integer. Since a^2 f^2
> > is divisible by f^2, so is e^2 d. However, d is square-free and e^2 is
> > coprime to f^2, since e and f are coprime. Therefor, f = +/- 1 and f^2 = 1.
> >
> > So b and f are units, which means that r and s are actually integers.
> > Therefor, -2r and r^2-ds^2 must be integers.
>
> Indeed, when b = 1. It is a bit different when b = 2.
--
Dik T. Winter
> Dik T. Winter wrote:
> > > with integer coefficients. Since a and b are coprime, b = +/- 1.
> > > Assume 1 for ease of notation.
> >
> > Or b = +/- 2...
>
> Drat. Ok, if b = 2 (assume a has the appropriate corresponding sign),
> then (a^2 f^2 - 4e^2d)/(4f^2) is an integer. Since a is coprime to 2,
> a^2 is not divisible by 4. Therefore f^2 is divisible by 4 and f is a
> multiple of 2. Suppose f=2k, k an integer.
>
> (a^2 f^2 - 4e^2d)/(4f^2) = (4a^2 k^2 - 4e^2d)/(16k^2)
> = (a^2 k^2 - e^2d)/(4k^2)
>
> Since k^2 divides a^2 k^2, k^2 must also divide e^2d. Since f and e are
> coprime, so are k and e. Therefor k^2 must divide d, which contradicts
> d being squarefree. Therefor, b =/= 2.
No, therefor k = +/- 1. Hence f = +/- 2. We can assume b = f = 2, and
find a and e odd. Now consider (a^2 - e^2.d)/4. a is odd, so
a^2 = 1 mod 4, and so for that quotient to be integer e^2.d = 1 mod 4 too.
e is odd, so e^2 = 1 mod 4 and so d = 1 mod 4. And indeed 1/2 + 3/2.sqrt(5)
is an algebraic integer.
But what is now shown is not what is wanted. It is shown that if the
quadratic polynomial is of the desired form that the roots have some
particular form. This does *not* show that if the roots are algebraic
integers, that the quadratic polynomial must have integer coeffecients.
The last is quite a bit more than elementary.
Timothy Murphy
> Yeah, _quadratic_ is the issue. We have the definition of
> "algebraic integer", and really nothing else. (We don't
> know what a ring is, we don't know what a primitive
> polynomial is, etc. These are exercises at the far end
> of the exercise sets in the text book, and they are
> just meant to demonstrate other integer-like systems.
> Part (a) is "show that if r+s\sqrt{d} is an algebraic
> integer, then it is of the form a+b\omega where a and be
> are integers and \omega=<appropriate surd>.)
This seems a strange approach to me.
Surely the basic property of "integer-like systems"
is that they form a ring, ie can be added and multiplied.
I would find it very odd to introduce algebraic integers
before pointing out that the rational integers form a ring.
Dik T. Winter
Yes, I misread. Anyhow, there is insufficient information for the
students to do it if they only have the definition of algebraic
integers. Hardy and Wright avoid the problem completely. They
define a norm in the quadratic fields and state that the numbers
with integer norm are the integers of the field. It is easy to
show that this definition gives a set closed under addition and
multiplication, so this is sufficient for the students to see that
there are more interesting integer like domains. That ultimately
these numbers are all algebraic integers is in itself not so very
interesting until much later. I think that, especially for students
starting with algebraic number theory, this is a good beginning.
(Even the proof that the algebraic integers with the standard
definition are closed under addition and multiplication is far from
trivial.)
Gerry Myerson
Dik T. Winter
...
> This seems a strange approach to me.
Indeed.
> Surely the basic property of "integer-like systems"
> is that they form a ring, ie can be added and multiplied.
> I would find it very odd to introduce algebraic integers
> before pointing out that the rational integers form a ring.
The problem with algebraic integers is that it is not trivial to show
they form a ring. So I think that even toying with them in general
is a bit to much in a starting number theory class.
Bart Goddard
> In article <pm6ud.43616$Z14....@news.indigo.ie>
> t...@birdsnest.maths.tcd.ie writes: ...
> > This seems a strange approach to me.
>
> Indeed.
>
> > Surely the basic property of "integer-like systems"
> > is that they form a ring, ie can be added and multiplied.
> > I would find it very odd to introduce algebraic integers
> > before pointing out that the rational integers form a ring.
>
> The problem with algebraic integers is that it is not trivial to show
> they form a ring. So I think that even toying with them in general
> is a bit to much in a starting number theory class.
For the record, this is a new "last chapter" in the next
edition of Ken Rosen's Text. It's a chapter on the Gaussian
integers, so at the point of this exercise, most of the things
needed for this exercise (norms, gcds, prime elements) have
been developed in the text for Z[i]. So the students aren't
completely fresh.
I finally decided that such students had probably done
long division of polynomials at some point in the past,
so I could write down the division algorithm without
further justification. (So I'm breaking the rules I
set down.) And we certainly have the well-ordering property,
so I can easily talk about _a_ minimal polynomial.
Here's a draft of my argument (for which comments are
welcome):
Suppose $\alpha=r+s\sqrt{-3}$ is an algebraic integer. Then it %42
is a root of a monic polynomial $f(x)$ with integer coefficients.
We may assume $f(x)$ has smallest positive degree of all
such polynomials. The case where $f(x)$ has degree less than two
is trivial, so we assume its degree is at least two.
Note that $\alpha$ is a root of $g(x)= (x-\alpha)(x-\overline
{\alpha})
= (x^2-2rx+r^2+3s^2)$. There exists an integer $p$ such that
$pg(x)$ has integer coefficients, and since $pg(\alpha)=0$, we
see that $pg(x)$ satisfies the requirements for $f(x)$ and so we
know, by the minimality of $f(x)$, that $\deg(f)=2$, say
$f(x)=ax^2+bx+c$. If we divide $f(x)$ by $g(x)$ we get
$f(x)=q(x)g(x)+r(x)$, with $\deg(r)<\deg(g)=2$. Since $f(x)$
and $g(x)$ have the same degree, we know that $q(x)=a$ is
constant.
Then we have $f(\alpha)=ag(\alpha)+r(\alpha)$, so that
$r(\alpha)=0$. But by our assumption, $\alpha$ can not be the
root of a
polynomial of degree 1 or 0, so $r(x)=0$ and we have
$f(x)=ag(x)$. Since $f(x)$ is monic, we have $a=1$ and so
$g(x)=f(x)=x^2+bx+c$. Using the quadratic formula, we find
the roots of $f(x)$ to be $(-b\pm\sqrt{b^2-4c})/2$, so $r$ and
$s$ are integers over 2, say $r=n/2$ and $s=m/2$. We check
that if $n$ and $m$ have opposite parity, then $f(x)$ will
not have integer coefficients. Therefore $n$ and $m$ have
the same parity and $\alpha$ must be of the form
$a+b\omega.$
Bart
Arturo Magidin
Bart Goddard <godd...@netscape.net> wrote:
[.snip.]
>I finally decided that such students had probably done
>long division of polynomials at some point in the past,
>so I could write down the division algorithm without
>further justification. (So I'm breaking the rules I
>set down.) And we certainly have the well-ordering property,
>so I can easily talk about _a_ minimal polynomial.
>
>Here's a draft of my argument (for which comments are
>welcome):
>
>Suppose $\alpha=r+s\sqrt{-3}$ is an algebraic integer. Then it %42
> is a root of a monic polynomial $f(x)$ with integer coefficients.
> We may assume $f(x)$ has smallest positive degree of all
> such polynomials. The case where $f(x)$ has degree less than two
> is trivial, so we assume its degree is at least two.
> Note that $\alpha$ is a root of $g(x)= (x-\alpha)(x-\overline
>{\alpha})
> = (x^2-2rx+r^2+3s^2)$. There exists an integer $p$ such that
> $pg(x)$ has integer coefficients, and since $pg(\alpha)=0$, we
> see that $pg(x)$ satisfies the requirements for $f(x)$ and so we
> know, by the minimality of $f(x)$, that $\deg(f)=2$, say
> $f(x)=ax^2+bx+c$.
Since you assumed f(x) was monic, you may as well set a=1 to begin with.
> If we divide $f(x)$ by $g(x)$ we get
> $f(x)=q(x)g(x)+r(x)$, with $\deg(r)<\deg(g)=2$.
... or r=0.
Be sure to note that q and r here are assumed to be polynomials with
rational coefficients (i.e., not necessarily integers).
> Since $f(x)$ and $g(x)$ have the same degree, we know that $q(x)=a$ is
>constant.
Especially if you are going to use "a" for something else later. (-:
> Then we have $f(\alpha)=ag(\alpha)+r(\alpha)$, so that
> $r(\alpha)=0$. But by our assumption, $\alpha$ can not be the
> root of a
> polynomial of degree 1 or 0, so $r(x)=0$ and we have
> $f(x)=ag(x)$. Since $f(x)$ is monic,
and so is g(x),
> we have $a=1$ and so
> $g(x)=f(x)=x^2+bx+c$.
In particular, g(x) has coefficients in Z.
> Using the quadratic formula, we find
> the roots of $f(x)$ to be $(-b\pm\sqrt{b^2-4c})/2$, so $r$ and
> $s$ are integers over 2, say $r=n/2$ and $s=m/2$.
I see why r is, but s is not so obvious to me yet. After all, r and s
are NOT the roots of f(x).
> We check
> that if $n$ and $m$ have opposite parity, then $f(x)$ will
> not have integer coefficients. Therefore $n$ and $m$ have
> the same parity and $\alpha$ must be of the form
> $a+b\omega.$
You know already that g(x) = (x^2-2rx+r^2+3s^2) = f(x)$, and that the
coefficients are in Z. This gives you that 2r is an integer, so r is
half an integer, say r=n/2.
You also know that r^2 + 3s^2 is an integer. If n is even, then 3s^2
must be an integer; that means that s must be an integer.
If n is odd, then 3s^2 must be equal to 4k+3/4 for some integer k, so
we conclude that s must be half an odd integer as well.
Arturo Magidin
[.snip.]
Ah, you got an error past me in my last reply!
>I finally decided that such students had probably done
>long division of polynomials at some point in the past,
>so I could write down the division algorithm without
>further justification. (So I'm breaking the rules I
>set down.) And we certainly have the well-ordering property,
>so I can easily talk about _a_ minimal polynomial.
>
>Here's a draft of my argument (for which comments are
>welcome):
>
>Suppose $\alpha=r+s\sqrt{-3}$ is an algebraic integer. Then it %42
> is a root of a monic polynomial $f(x)$ with integer coefficients.
> We may assume $f(x)$ has smallest positive degree of all
> such polynomials. The case where $f(x)$ has degree less than two
> is trivial, so we assume its degree is at least two.
> Note that $\alpha$ is a root of $g(x)= (x-\alpha)(x-\overline
>{\alpha})
> = (x^2-2rx+r^2+3s^2)$. There exists an integer $p$ such that
> $pg(x)$ has integer coefficients, and since $pg(\alpha)=0$, we
> see that $pg(x)$ satisfies the requirements for $f(x)$ and so we
> know, by the minimality of $f(x)$, that $\deg(f)=2$,
No, we do not.
Recall that f(x) was defined to be a *monic* polynomial with integer
coefficients which has least degree among all *monic* polynomials with
integer coefficients. Since pg(x) has leading coefficient p, you can
only conclude that deg(f)<= deg(pg) if you assume that p=+/- 1, which
amounts to assuming that g(x) has integer coefficients in the first
place, which was the whole point of this digression.
Rather, at this point, if deg(f)>2, then you can divide f(x) by g(x)
in Q[x] to get
f(x) = q(x)g(x) + r(x) with deg(r)<deg(g) or r=0,
and deduce that r(x) = 0. Then you would need to invoke Gauss's lemma
to deduce that since f(x)=q(x)g(x) in Q[x], then f(x) factors over
Z[x], which contradicts the minimality of the degree of f(x). From
this you can conclude that deg(f)<=2, and then you can proceed as before.
Dik T. Winter
...
> For the record, this is a new "last chapter" in the next
> edition of Ken Rosen's Text. It's a chapter on the Gaussian
> integers, so at the point of this exercise, most of the things
> needed for this exercise (norms, gcds, prime elements) have
> been developed in the text for Z[i]. So the students aren't
> completely fresh.
Was it shown that *all* algebraic integers of the form 'a + b.i' are those
with integral 'a' and 'b'? As Arturo already wrote, that requires quite a
bit more than what is developed at that moment. The definition of algebraic
integers only states that the number is a root of *some* monic polynomial
with integer coefficients. To prove that some particular number (like
'(1 + i)/2') is not an algebraic integer you need to show that it is not
the root of *any* monic polynomial with integer coefficients. Off-hand,
how would you like to show with elementary means that '(1 + i)/2' is
*not* an algebraic integer?
I honestly think that the best way to put exercises to the students is
to consider other quadratic fields, with a norm function and defining
integers to be those that have integer norm. This results in interesting
division properties. It also clearly shows that the rings of those
"integers" are integer-like, but sometimes also have strange properties.
And they can at least prove that "integers" so defined are indeed
algebraic integers (but not the other way around, and this is what you
seem to wish). For students that have just seen the Gaussian integers,
what you want them to do is way beyond their capabilities at that point.
Arturo Magidin
>I honestly think that the best way to put exercises to the students is
>to consider other quadratic fields, with a norm function and defining
>integers to be those that have integer norm.
What norm? Certainly not the usual norm.
For example, in Q(sqrt(-15)), the norm of (1/4) + (1/4)*sqrt(-15) is
1, an integer, yet it is clearly not an algebraic integer.
In fact, any root of an irreducible polynomial of the form x^2 + ax +
b, with b an integer, will have integer norm but will only be an
algebraic integer if a is also an integer.
>This results in interesting
>division properties. It also clearly shows that the rings of those
>"integers" are integer-like, but sometimes also have strange properties.
>And they can at least prove that "integers" so defined are indeed
>algebraic integers (but not the other way around, and this is what you
>seem to wish).
Ah; so you're dealing with an order rather than with the ring of
algebraic integer. Okay then....
Dik T. Winter
> In article <I8JAt...@cwi.nl>, Dik T. Winter <Dik.W...@cwi.nl> wrote:
>
> >I honestly think that the best way to put exercises to the students is
> >to consider other quadratic fields, with a norm function and defining
> >integers to be those that have integer norm.
>
> What norm? Certainly not the usual norm.
The usual norm, for quadratic fields.
> For example, in Q(sqrt(-15)), the norm of (1/4) + (1/4)*sqrt(-15) is
> 1, an integer, yet it is clearly not an algebraic integer.
Yes, in some cases such a norm (as Hardy & Wright call it) will not
result in algebraic integers. However, at the level the students
apparently are, they would have difficulty proving that it is *not*
an algebraic integer. They have just touched the Gaussian integers.
Nevertheless, while they are not algebraic integers, they are integer-like,
and that was the purpose; to show that there were interesting other
integer-like rings.
But I was indeed wrong when I said that they could prove that the
"integers" so defined were algebraic integers. I shouls really pick
up again Hardy & Wright to see how they do it.
Timothy Murphy
> > For example, in Q(sqrt(-15)), the norm of (1/4) + (1/4)*sqrt(-15) is
> > 1, an integer, yet it is clearly not an algebraic integer.
>
> Yes, in some cases such a norm (as Hardy & Wright call it) will not
> result in algebraic integers.
Isn't this the norm (pun intended)?
If f is an automorphism of the extension K/k
then x/f(x) will have norm 1,
but will not normally be an algebraic integer.
> However, at the level the students
> apparently are, they would have difficulty proving that it is *not*
> an algebraic integer. They have just touched the Gaussian integers.
> Nevertheless, while they are not algebraic integers, they are
> integer-like, and that was the purpose; to show that there were
> interesting other integer-like rings.
I wouldn't have thought numbers with norm 1 are at all "integer-like".
Does the sum of two such numbers always have norm 1?
Arturo Magidin
Timothy Murphy <t...@birdsnest.maths.tcd.ie> wrote:
>Dik T. Winter wrote:
>
>> > For example, in Q(sqrt(-15)), the norm of (1/4) + (1/4)*sqrt(-15) is
>> > 1, an integer, yet it is clearly not an algebraic integer.
>>
>> Yes, in some cases such a norm (as Hardy & Wright call it) will not
>> result in algebraic integers.
>
>Isn't this the norm (pun intended)?
>If f is an automorphism of the extension K/k
>then x/f(x) will have norm 1,
>but will not normally be an algebraic integer.
>
>> However, at the level the students
>> apparently are, they would have difficulty proving that it is *not*
>> an algebraic integer. They have just touched the Gaussian integers.
>> Nevertheless, while they are not algebraic integers, they are
>> integer-like, and that was the purpose; to show that there were
>> interesting other integer-like rings.
>
>I wouldn't have thought numbers with norm 1 are at all "integer-like".
>Does the sum of two such numbers always have norm 1?
Certainly not. The two roots of x^2 - (1/2)x + 1 have norm 1 and add
up to 1/2, which has norm 1/4.
Dik T. Winter
> Dik T. Winter wrote:
>
> > > For example, in Q(sqrt(-15)), the norm of (1/4) + (1/4)*sqrt(-15) is
> > > 1, an integer, yet it is clearly not an algebraic integer.
> >
> > Yes, in some cases such a norm (as Hardy & Wright call it) will not
> > result in algebraic integers.
>
> Isn't this the norm (pun intended)?
> If f is an automorphism of the extension K/k
> then x/f(x) will have norm 1,
> but will not normally be an algebraic integer.
Yes, I was horribly wrong. I think a combination of bad memory and lack
of sleep, or whatever. Hardy and Wright do develop Q(sqrt(-1)) and
Q(sqrt(-3)) without regard to algebraic integers, but when they get
serious with quadratic fields they seriously prove how to get all
"integers" in the field and show that they are "algebraic integers".
Section 14.2 is about this stuff. They first show that each algebraic
integer has a minimal polynomial, and next show that algebraic integers
have a specific form in quadratic fields.
On the other hand, they do *not* show that the algebraic integers form
a ring. The simplest proof of that I have found in Van der Waerden,
but that requires quite a bit more.
Robert Israel
>On the other hand, they do *not* show that the algebraic integers form
>a ring. The simplest proof of that I have found in Van der Waerden,
>but that requires quite a bit more.
Time to dust off my favourite four-line proof:
A complex number is an algebraic integer iff it is an eigenvalue of a
square matrix of integers. If x and y are eigenvalues of A and B
respectively, then x+y is an eigenvalue of (A @ I) + (I @ B) and
xy is an eigenvalue of A @ B, where @ denotes tensor product.
Dave Boyd tells me he heard this from Olga Taussky in the 60's.
Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
David C. Ullrich
>In article <I8qp8...@cwi.nl>, Dik T. Winter <Dik.W...@cwi.nl> wrote:
>
>>On the other hand, they do *not* show that the algebraic integers form
>>a ring. The simplest proof of that I have found in Van der Waerden,
>>but that requires quite a bit more.
>
>Time to dust off my favourite four-line proof:
>
>A complex number is an algebraic integer iff it is an eigenvalue of a
>square matrix of integers.
Hmm. One direction is clear even to me, knowing no algebra: the
characteristic polynomial of a matrix is monic, fine. For the
other direction: Is it obvious and/or true that any (irreducible?)
monic polynomial with integer coefficients is (a factor of?) the
characteristic polynomial of some integer-valued matrix?
>If x and y are eigenvalues of A and B
>respectively, then x+y is an eigenvalue of (A @ I) + (I @ B) and
>xy is an eigenvalue of A @ B, where @ denotes tensor product.
>
>Dave Boyd tells me he heard this from Olga Taussky in the 60's.
>
>Robert Israel isr...@math.ubc.ca
>Department of Mathematics http://www.math.ubc.ca/~israel
>University of British Columbia Vancouver, BC, Canada
************************
David C. Ullrich
Dik T. Winter
> On 15 Dec 2004 05:53:20 GMT, isr...@math.ubc.ca (Robert Israel) wrote:
> >A complex number is an algebraic integer iff it is an eigenvalue of a
> >square matrix of integers.
>
> Hmm. One direction is clear even to me, knowing no algebra: the
> characteristic polynomial of a matrix is monic, fine. For the
> other direction: Is it obvious and/or true that any (irreducible?)
> monic polynomial with integer coefficients is (a factor of?) the
> characteristic polynomial of some integer-valued matrix?
Yup. You can construct the companion matrix of the polynomial. This
consists of 1 along the subdiagonal and the negatives of the coefficients
of the polynomial (minus the leading 1) along the top row and 0 elsewhere.
The characteristic polynomial is the original polynomial.
On the other hand, the remainder is less trivial if you do know no
algebra:
> >If x and y are eigenvalues of A and B
> >respectively, then x+y is an eigenvalue of (A @ I) + (I @ B) and
> >xy is an eigenvalue of A @ B, where @ denotes tensor product.
BTW, this is similar to the proof in Van der Waerden, but he does
not require knowledge of algebra.
Robin Chapman
> On 15 Dec 2004 05:53:20 GMT, isr...@math.ubc.ca (Robert Israel) wrote:
>
>>In article <I8qp8...@cwi.nl>, Dik T. Winter <Dik.W...@cwi.nl> wrote:
>>
>>>On the other hand, they do *not* show that the algebraic integers form
>>>a ring. The simplest proof of that I have found in Van der Waerden,
>>>but that requires quite a bit more.
>>
>>Time to dust off my favourite four-line proof:
>>
>>A complex number is an algebraic integer iff it is an eigenvalue of a
>>square matrix of integers.
>
> Hmm. One direction is clear even to me, knowing no algebra: the
> characteristic polynomial of a matrix is monic, fine. For the
> other direction: Is it obvious and/or true that any (irreducible?)
> monic polynomial with integer coefficients is (a factor of?) the
> characteristic polynomial of some integer-valued matrix?
As Dik said, the maigic words are "companion matrix". I learnt this
proof from Peter Cameron in c. 1982. In my "notes on algebraic numbers"
(see webpage) I give an even more simple-minded version of this, avoiding
even companion matrices :-)
--
Robin Chapman, www.maths.ex.ac.uk/~rjc/rjc.html
"Lacan, Jacques, 79, 91-92; mistakes his penis for a square root, 88-9"
Francis Wheen, _How Mumbo-Jumbo Conquered the World_
Timothy Murphy
>>On the other hand, they do *not* show that the algebraic integers form
>>a ring. The simplest proof of that I have found in Van der Waerden,
>>but that requires quite a bit more.
> A complex number is an algebraic integer iff it is an eigenvalue of a
> square matrix of integers. If x and y are eigenvalues of A and B
> respectively, then x+y is an eigenvalue of (A @ I) + (I @ B) and
> xy is an eigenvalue of A @ B, where @ denotes tensor product.
While this is quite a slick proof,
it doesn't really throw much light on _why_ the result holds.
(Also the tensor product of 2 matrices is quite a difficult concept.
How does one show that the eigenvalues of A@B
are the products of the eigenvalues?)
To my mind, the best proof - even though it uses a bit of algebra,
and is slightly longer - depends on the Lemma that
c in C is an algebraic integer iff there is a finitely-generated group A < C
such that cA < A.
This fits in rather well with the Lemma that
c in C is algebraic iff there is a finite-dimensional vector subspace V < C
such that cV < V.
Bill Dubuque
>> a ring. The simplest proof of that I have found in Van der Waerden,
>> but that requires quite a bit more.
>
> Time to dust off my favourite four-line proof:
>
> A complex number is an algebraic integer iff it is an eigenvalue of a
> square matrix of integers. If x and y are eigenvalues of A and B
> respectively, then x+y is an eigenvalue of (A @ I) + (I @ B) and
> xy is an eigenvalue of A @ B, where @ denotes tensor product.
>
> Dave Boyd tells me he heard this from Olga Taussky in the 60's.
Actually "it's already in Dedekind" as Noether often said.
However Taussky did do much pioneering work in the matrix
representational approach to algebraic number theory and she
played a major role in popularizing this viewpoint, so it's
not too surprising to see this mistakenly attributed to her.
An introduction to some of Taussky's work here may be found
in her two appendices to Harvey Cohn's excellent textbook:
A classical invitation to algebraic numbers and class fields.
Of course one doesn't need to explicitly introduce tensor products.
Instead, as is well-known, one may proceed more simply as follows
(for convenience this is based upon Robin Chapman's notes [1] but,
as I mentioned, it already occurs in Dedekind over 100 years ago)
THEOREM 1. If b and c are algebraic integers so too are b+c and bc.
PROOF. Suppose b and c are algebraic integers. The idea of the proof
is to find a nonzero vector v and two integer matrices B and C with
Bv = bv, Cv = cv. Then b+c, bc are eigenvalues of B+C, BC resp.
since (B+C)v = Bv + Cv = bv + cv = (b+c)v
and (B C)v = B(Cv) = B(cv) = cBv = bc v
Since B+C and BC have integer coefficients, we conclude by Lemma 1
that b+c and bc are both algebraic integers. It remains to show that
such matrices B and C exist. Suppose b^n + b_1 b^(n-1) +...+ b_n = 0
and c^m + c_1 c^(m-1) +...+ c_m = 0, where the b_j, c_k are integers.
T
Let v be the mn by 1 vector (b^j c^k : 0 <= j < n, 0 <= k < m)
Consider bv. The entries in this vector all have the form b^(j+1)c^k
where 0 <= j < n, 0 <= k < m. If j+1 < n this is already an entry in v;
if j+1 = n it equals
k n k n-1 n-2
c b = c (- b b - b b - ... - b b - b )
1 2 n-1 n
In all cases b^(j+1)c^k is a linear combination, with integer coefficients,
of entries in v. Therefore there exists an integer matrix B with Bv = bv.
Similarly there exists an integer matrix C with Cv = cv. QED
Of course nowadays this is all expressed much more concisely and
elegantly in the language of (finitely-generated) modules, the
theory of which was constructed by Dedekind as he iteratively
revised and polished his manuscripts on algebraic number theory.
--Bill Dubuque
[1] Robin Chapman, Notes on Algebraic Numbers
http://www.maths.ex.ac.uk/~rjc/notes/algn.dvi
http://www.maths.ex.ac.uk/~rjc/notes/algn.ps
http://www.maths.ex.ac.uk/~rjc/notes/algn.pdf
http://www.maths.ex.ac.uk/~rjc/rjc.html
Robert Israel
Timothy Murphy <t...@birdsnest.maths.tcd.ie> wrote:
>Robert Israel wrote:
>> A complex number is an algebraic integer iff it is an eigenvalue of a
>> square matrix of integers. If x and y are eigenvalues of A and B
>> respectively, then x+y is an eigenvalue of (A @ I) + (I @ B) and
>> xy is an eigenvalue of A @ B, where @ denotes tensor product.
>While this is quite a slick proof,
>it doesn't really throw much light on _why_ the result holds.
>(Also the tensor product of 2 matrices is quite a difficult concept.
>How does one show that the eigenvalues of A@B
>are the products of the eigenvalues?)
If v is an eigenvector of A for eigenvalue x and w is an eigenvector of
B for eigenvalue y, then (A @ B) (v @ w) = (Av) @ (Bw) = x y (v @ w).
There's nothing really difficult, to my mind, about the tensor product of
matrices as a concept. You can do it quite concretely as the Kronecker
product. Indices for A@B correspond to pairs of indices for A and B
respectively, and (A@B)_{(ij),(kl)} = A_{ik} B_{jl}. All you need to
verify is that (A@B)(v@w)=(Av)@(Bw).