wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> putnam exam (pure math) >> tough number theory prob.
(Message started by: LeoYard on Jun 10th, 2008, 12:29pm)

Title: tough number theory prob.
Post by LeoYard on Jun 10th, 2008, 12:29pm
Let w=(-1 +(-3)^0.5))/2 and note that w^2=-1 -w.
Consider the integral domain Z +Zw, and let U(Z+Zw) be the set of units.

Prove that U(Z+Zw)=(+1,-1, +w, -w ,+w^2, -w^2).

Here's my next question:

Let m be an integer with m = 1 (mod 4) and m less than -3.
Prove that the set of units U(Z +Z((1 + sqrt(m)/2) = (+1, -1)

Title: Re: tough number theory prob.
Post by Aryabhatta on Jun 10th, 2008, 12:33pm
Is this homework?

Title: Re: tough number theory prob.
Post by LeoYard on Jun 10th, 2008, 1:07pm

on 06/10/08 at 12:33:23, Aryabhatta wrote:
Is this homework?


Yes, i need some help to get me started.

I need to add:

For a given integral domain A (say), a member 'i' (say) of this set is called a unit if there exists another element 'j' (say) in A such that i*j=1.

We denote the set of all the units of A as U(A)

In the first question, I'm saying that the only units for the integral domain (Z +Zw) are +1, -1, +w and -w.


Title: Re: tough number theory prob.
Post by Eigenray on Jun 10th, 2008, 1:31pm
What do you know about norms?

Title: Re: tough number theory prob.
Post by LeoYard on Jun 10th, 2008, 2:47pm
I'm a bit overwhelmed by algebraic number theory.


Quote:
What do you know about norms?


I've started Field norm in algebraic number theory. I'm embarrassed to say that I don't know how to tackle this problem.

Title: Re: tough number theory prob.
Post by LeoYard on Jun 10th, 2008, 10:23pm
I don't know much about "norms". I'm on chapter 1.
My book in chapter 9 defines them as follows:

If K is an algebraic number field of degree n, and 'r' is an element of K then the norm of 'r' is

f_1(r)*f_2(r)*.....*f_n(r)

where f_i: K to C (set of complex numbers) are the n distinct monomorphisms from K to C.

There isn't anything in chapter 1 of my text which discusses it, so i'm supposed to solve this without them.

Title: Re: tough number theory prob.
Post by Eigenray on Jun 11th, 2008, 8:21am
Suppose x*y = 1.  Here are two approaches:

1. What do you know about the norms of x and y?

2. If x=a+bw, y=c+dw, find c,d in terms of a,b.  When are these integers?

Title: Re: tough number theory prob.
Post by LeoYard on Jun 11th, 2008, 1:00pm
I'm going with approach #2

First if If x=a+bw, y=c+dw then 1 = x*y = (a +bw)(c +dw)= ac + (ad +bc)w + (bd)w^2.

Now w^2 = -w -1. Hence (ac) + (ad +bc)w + (bd)w^2 = (ac - bd) + (ad +bc -bd)w = 1

This implies that ac - bd = 1 and that ad +bc -bd = 0 (eg bd =ad +bc).

I'm not sure where it is I'm suppose to go from here.

Title: Re: tough number theory prob.
Post by Eigenray on Jun 11th, 2008, 3:27pm
You can solve the system of equations for c and d.  Or, you can just rationalize 1/(a+bw) = (a+bw2)/((a+bw)(a+bw2)).  You should find that a2-ab+b2 divides both b and a-b.  By considering gcd(a,b) you can show a2-ab+b2 = 1 (-1 is impossible).

It may be easier to express elements of Z[w] as (a + bhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(-3))/2 instead, where a,b are integers of the same parity.

Do you know how to show that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gifi are the only units of the Gaussian integers Z[i]?  The proof is much the same.

Title: Re: tough number theory prob.
Post by LeoYard on Jun 11th, 2008, 11:12pm
Sorry but I'm afraid I couldn't follow your reasoning for much of any of that. Can you please show me either how it is you can solve for c and d, or the other procedure you suggested?


Yes I do know how to prove that the set of units for Z(i) is (+1, -1, +i, -i). It goes as follows:

Let x=a + bi be a unit. Then there exists a y= c + di such that (a + bi)(c + di)=1.

This implies that ac - bd = 1 and ad + bc = 0 (call (1))

Now consider the identity (a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2.

From (1) we have that (a^2 + b^2)(c^2 + d^2) = 1.

From this, it follows that a^2 + b^2 = 1, which implies that (a,b) = (+/-1,0) or (0,+/-1).

It follows then that x must be in the set (+1, -1, +i, -i).

Thus U(Z(i)) is a subset of (+1, -1, +i, -i). On the other hand, it can be easily checked that all the elements in (+1, -1, +i, -i) are also units. Hence (+1, -1, +i, -i) is subset of U(Z(i)).

Hence U(Z(i)) = (+1, -1, +i, -i).

Title: Re: tough number theory prob.
Post by Eigenray on Jun 12th, 2008, 12:04am

on 06/11/08 at 23:12:55, LeoYard wrote:
Now consider the identity (a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2.

This identity is precisely the multiplicative property of the norm on Z[i].  Considering the norm on Z[w] you should find a similar identity that will allow you to solve the problem.

Title: Re: tough number theory prob.
Post by LeoYard on Jun 12th, 2008, 11:37am
Thanx, i've just experienced a Eureka moment!

First I'll state the following property of norms:

If N is the norm on Z(w) then we have that the following property holds:

N(ab)= N(a)N(b)

Hence N(a + bw)N(c + dw) = N((a +bw)(c + dw)).

It follows that (a^2 - b^2 -b^(2)w)(c^2 -d^2 - d^(2)w) = (ac - bd)^2 - (-bd + ad + bc)^2 - (-bd + ad +bc)^2w

Now we know from before that ac - bd = 1 and that -bd + ad + bc = 0.

Thus we have that (a^2 - b^2 -b^(2)w)(c^2 -d^2 - d^(2)w) = 1.

However this implies that b = d = 0

This gives us a^2 * c^2 = 1.

It follows that a= +1 or -1.

Hence U(Z(w)) is in the set (+1, -1). However a quick check also shows that (+1, -1) is also in the set U(Z(w)).

Thus U(Z(w)) = (+1, -1).
....................................................................
Does the property N(ab) = N(a)N(b) hold for any integral domain?

Furthermore is N(x) also a non-negative function over integral domains?

Title: Re: tough number theory prob.
Post by Eigenray on Jun 12th, 2008, 12:26pm

on 06/12/08 at 11:37:21, LeoYard wrote:
Hence N(a + bw)N(c + dw) = N((a +bw)(c + dw)).

It follows that (a^2 - b^2 -b^(2)w)(c^2 -d^2 - d^(2)w) = (ac - bd)^2 - (-bd + ad + bc)^2 - (-bd + ad +bc)^2w

I'm not sure where you got that formula from.  The conjugate of a+bw is a+bw2, so

N(a+bw) = (a+bw)(a+bw2)
= a2 + ab(w+w2) + b2w3
= a2 - ab + b2.

This leads to the identity
(a2 - ab + b2)(c2 - cd + d2) = (ac-bd)2 - (ac-bd)(bc+ad-bd) + (bc+ad-bd)2.

However, this identity isn't really what's important.  What's important is the following: if xy=1, then N(x)N(y) = N(xy) = 1, and N(x), N(y) are integers when x,y http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif Z[w] (or more generally, when they are algebraic integers, i.e., they satisfy monic polynomials with integer coefficients).  Furthermore, for imaginary quadratic number fields, the norm is positive definite, so there will only be finitely many possibilities for x, y.


Quote:
Hence U(Z(w)) is in the set (+1, -1).

You should find that the units are http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gifw, and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gifw2.


Quote:
Does the property N(ab) = N(a)N(b) hold for any integral domain?

The norm is not defined for an arbitrary integral domain.  But if you are working in a number field, then yes.  It follows from the formula you gave, since each embedding K -> C is multiplicative.


Quote:
Furthermore is N(x) also a non-negative function over integral domains?

No.  For one thing, N(-1) = (-1)[K:Q], so [K:Q] must be even.  But even in the case where K/Q is quadratic, it is only true for imaginary number fields.  E.g., N(a+bhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifd) = a2 - d b2.  This takes on negative values iff d>0.

Title: Re: tough number theory prob.
Post by LeoYard on Jun 12th, 2008, 2:22pm
I thought it followed by definition that the conjugate of a + bw was a - bw. I guess its just the sign in front of the sqrt(-3) that changes, right?

Title: Re: tough number theory prob.
Post by Eigenray on Jun 12th, 2008, 3:14pm
Yes that's right.  Complex conjugation is the unique non-trivial automorphism of K = Q(w).  It sends http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(-3) to -http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(-3), and w to w2.  Alternatively, the minimal polynomial of w is x2+x+1=0, which has roots w and w2, so these two elements are conjugate.

Title: Re: tough number theory prob.
Post by LeoYard on Sep 27th, 2008, 5:05pm
I was on holidays, now I'm back to number theory.

How to prove that the following is an integral domain:

Z + Zk + Zk^2 where k is a root of the cubic equation k^3 - k^2 + 1 = 0.

The parts I'm having trouble with are the following:

(1) Proving that there are no zero divisors.
(2) Showing that it is closed under multiplication.

--------
If D is an integral domain then U(D) is an Abelian group with respect to multiplication (Theorem)


Title: Re: tough number theory prob.
Post by Eigenray on Sep 27th, 2008, 7:52pm
To show that it is closed under multiplication, you will need to express k3 and k4 in terms of 1,k,k2.  The essential reason this works is that the polynomial x3-x2+1 is monic.

Now the short answer for why it is an integral domain is because it is a subring of a field.  I don't know if this makes sense to you, but in general, Z[x]/f(x) is a domain iff Q[x]/f(x) is a field iff f(x) is irreducible.

Title: Re: tough number theory prob.
Post by LeoYard on Sep 29th, 2008, 1:12pm

on 09/27/08 at 19:52:24, Eigenray wrote:
To show that it is closed under multiplication, you will need to express k3 and k4 in terms of 1,k,k2.  The essential reason this works is that the polynomial x3-x2+1 is monic.

Now the short answer for why it is an integral domain is because it is a subring of a field.  I don't know if this makes sense to you, but in general, Z[x]/f(x) is a domain iff Q[x]/f(x) is a field iff f(x) is irreducible.


Thanks Eigenray.

I looked at  Z+Zi where i^2 + 1 = 0, first.

I'm studying Euclidean rings, however the rings we appear to be focused on in class are integral domains.

There is a theorem in my textbook which says the following:

Let m = 2,3 (mod 4) be a negative squarefree integer. Then Z + Zsqrt(m) is not a Euclidean domain for any integer m less than -7
Prove that Z + Zsqrt(m) is not even an Almost Euclidean domain.

How to show that there are no Almost Euclidean domains Z + Zsqrt(m) where m is squarefree and less than -7.

I haven't been able to prove the case when m = -7.

I got the feeling that Z + Zsqrt(-7) is a P.ID/Almost Euclidean since for many prime p such that (m/p) = 1, we have that p x^2 - my^2 for some integers x and y.

necessary condition for P.I.D's.,  but not be sufficient.

Title: Re: tough number theory prob.
Post by Eigenray on Sep 30th, 2008, 2:23am
What is an Almost Euclidean domain?  If you mean in the sense of Campoli it is equivalent to PID.

The ring http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm] is a PID for m=-1,-2, but never for m < -2 square-free.  This is because I = (2, m+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm) is not principal.  Suppose I = (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif).  Then http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif | 2 implies N(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif) | N(2) = 4, so N(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif) = 1,2, or 4.  Check the following: If N(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif)=1, then http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif is a unit, but I is not the unit ideal.  N(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif)=2 is impossible.  And N(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif)=4 would imply that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/alpha.gif and 2 are associates, meaning I = (2), which is impossible.

However, when m=1 mod 4 (as -7 is), http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm] is the wrong thing to look at.  Given a number field K, one should look at the ring of all algebraic integers of K: the elements of K which are roots of monic polynomials with integer coefficients.  If m=2,3 mod 4, then the only algebraic integers in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm) are a+bhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm, with a,b http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif.  But if m=1 mod 4, then (1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm)/2 is an algebraic integer: it is a root of x2 - x + (1-m)/4.  So the correct ring to look at when m=1 mod 4 is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[(1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm)/2] = { (a+bhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm)/2 | a,b integers of the same parity }.

For -m=3,7,11, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[(1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm)/2] is a PID; in fact they are Euclidean with respect to the field norm.  For m=-15 (or any composite square-free negative m), this ring is not a PID.  For -m=19, 43, 67, 163, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[(1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm)/2] is a PID which is not Euclidean.  It is a deep theorem that there are no other imaginary quadratic number fields for which the ring of integers is a PID.

Title: Re: tough number theory prob.
Post by LeoYard on Sep 30th, 2008, 1:39pm
Thanks Eigenray. Before I can answer directly to your post, I need to ask few questions to have this stuff clear in my mind.

A peripheral question:

When we say that a ring is never a PID because it is never integrally closed, does it mean that it isn't closed under multiplication?

There are general formulas for the class numbers of quadratic rings that can be used to check for the PID property

to be found at

http://mathworld.wolfram.com/ClassNumber.html

I'm interested to know how it is that the class number of a ring is suppose to be related to how well a ring is to being a unique factorization domain.
With regards to P.I.D's, I'm interested in which values of m we have that Z + Zsqrt(m) is P.I.D. I already know the answer to this when m is negative (except for m = -7), but I don't know the answer to this when m is a positive integer.

for m = 1 (mod 4) is the ring Z+Zsqrt(m) a PID?

do we know for which positive value m this ring is a PID?

is the ring Z+Z*((sqrt(m)+1)/2) is a PID for m=1 (mod 4)?

I went to "Class number problem" at http://en.wikipedia.org/wiki/Class_number_problem




Title: Re: tough number theory prob.
Post by Eigenray on Oct 1st, 2008, 2:53am

on 09/30/08 at 13:39:37, LeoYard wrote:
When we say that a ring is never a PID because it is never integrally closed, does it mean that it isn't closed under multiplication?

No.  For example, R=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm] is always closed under multiplication: (a+bhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm)(c+dhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm) = (ac+mbd)+(ad+bc)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm.  But it is not integrally closed if m=1 mod 4 (and m is not a square).  The element x = (1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm)/2 of the field of fractions of R is integral over R, being a root of
x2 - x + (1-m)/4 = 0,
but it is not an element of R.

Since any PID is integrally closed (the rational roots theorem holds equally well over any PID), this means that R can't be a PID.  In fact, (2,1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm) isn't principal in R.  But over the larger ring S=http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[(1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm)/2], 1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm is divisible by 2, so (2,1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm) = (2) is principal in S.  But S may or may not be a PID.


Quote:
I'm interested to know how it is that the class number of a ring is suppose to be related to how well a ring is to being a unique factorization domain.

Well, it's related in the sense that h=1 iff R is a UFD.  A more accurate statement is that the class number tells you how close R is to being a PID: the class number tells you how many classes of ideals there are, where we say two ideals have the same class if they 'differ' by a principal ideal.

Another way of looking at it is that in the ring of integers of a number field, we have unique factorization of ideals.  What we would like, however, is unique factorization of elements.  Each element x gives an ideal (x), but not every ideal is of this form.  The class number measures the extent of this failure in a precise way.

For example, take R = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{-5}].  This has class number 2, with class group generated by the class of (2,1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{-5}).  So for any ideal I, exactly one of I and I*(2,1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{-5}) will be principal, so we can always find an element x such that either (x) = I or (x) = I*(2,1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{-5}).

If you know about modules there is another way of putting it.  Any ideal I of R is an R-module, and I http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cong.gif R as R-modules iff I is principal.  More generally, if I ~ J in the class group of R, then J = xI for some x in the quotient field of K, and multiplication by x gives an R-module isomorphism from I to J.  Conversely, suppose I http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cong.gif J as R-modules.  Since the ideal classes form a group, there is an ideal I' such that I' I = (x) is principal.  Since I' I http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cong.gif I' J as R-modules, I' J is also principal, so J ~ I'-1 ~ I.  That is, two ideals of R are isomorphic as R-modules iff they are in the same ideal class, so the class group of R is also the set of isomorphism classes of ideals of R.


Quote:
for m = 1 (mod 4) is the ring Z+Zsqrt(m) a PID?

No, because it is not integrally closed (for m not a square).


Quote:
do we know for which positive value m this ring is a PID?

is the ring Z+Z*((sqrt(m)+1)/2) is a PID for m=1 (mod 4)?

Sometimes, but nobody knows whether they are PIDs infinitely often.  See [link=http://www.research.att.com/~njas/sequences/A003172]A003172[/link].

Title: Re: tough number theory prob.
Post by LeoYard on Oct 1st, 2008, 1:59pm
Question: is the ring Z+Z*((sqrt(m)+1)/2) is a PID for m=1 (mod 4)?

You said: Sometimes, but nobody knows whether they are PIDs infinitely often

My new question:  is this an unsolved problem for even when m is negative?

Title: Re: tough number theory prob.
Post by Eigenray on Oct 1st, 2008, 3:15pm
For m=1 mod 4, m < 0, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[(1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifm)/2] is a PID only for -m = 3,7,11,19,43,67,163.  In addition to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[i] and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif{-2}], these are the only rings of integers of imaginary quadratic number fields to be PIDs, as you can see on the [link=http://en.wikipedia.org/wiki/Class_number_problem]class number problem[/link] page.

Title: Re: tough number theory prob.
Post by BenVitale on Oct 17th, 2008, 4:15pm
Interesting discussions going on here!

Why isn't the remainder symbol "rem" being used? I heard it being used in some lectures, but I couldn't find in textbooks.

Say we have the set {..., -1, +2, +5, +8, +11, +14, ...}
These numbers all leave a remainder of 2 when divided by 3.
We write: rem(5,3) = rem(8,3) = rem(11,3) =... = 2

If a = b (mod n) would that mean:

a = (rem(a,n)) (mod n)
a = b (mod n) iff (rem(a,n)) = (rem(b,n))

Title: Re: tough number theory prob.
Post by Eigenray on Oct 18th, 2008, 8:22am
Probably because it's not very convenient.

It's a slight abuse of notation to say that "a = b (mod n)", because while "b mod n" is well-defined (it is the image of b in the quotient http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif/nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif or the set of elements of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif congruent to b modulo n), it is not really equal to a.  So more technically correct notation would be "a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif (b mod n)", or "(a mod n) = (b mod n)".  But it is easier to just write "a = b", and then write "mod n" at the end to mean that we are modifying what it means to be equal.

So really it defines a new relation http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gifn where a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gifn b iff a and b are congruent modulo n.  When n is understood this is usually just written http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif.  Of course this notation is used much more generally, if we want to mod out a group by a subgroup, a module by a submodule, a space by a group action, etc.  One can also draw bars over a and b to denote elements of the quotient, and write a-bar = b-bar, or use brackets: [a] = [b], when one is thinking of equivalence classes.

Title: Re: tough number theory prob.
Post by Grimbal on Oct 18th, 2008, 11:54pm
The way I see it is that the correct notation is:
  a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif b (mod n)
and it should be understood as
  a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif b       (please understand http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif as the equivalence modulo n)
So, "(mod n)" is not part of the expression, but gives a context to it.

The equivalence
  a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif b  (mod n)
means
  a = b + k·n   for some k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif
which implies
  rem(a,n) = rem(b,n)

This has nothing to do with the binary operator 'mod' that you can see in some computer languages.

In mathematics you use "http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif ... (mod n)" equivalence and express the remainder with a rem(x,n) function, while in some computer languages, or calculators, you use "mod" as an operator to compute a remainder.

Title: Re: tough number theory prob.
Post by Michael Dagg on Nov 7th, 2008, 12:23pm
Nice discussion and as pointed out, this is an interesting
problem as well as ones like it. It is crucial in many problems
to know the group of units in an algebraic number field.
(For example, when "ideals", then viewed as "ideal numbers" were
first invented by Kummer, it was in the context of proving Fermat's
Last Theorem. He got as far as calculating that some important
ideal would be principal, but then had to wrestle with the possible
ways that the generator could be presented; the options differ
from one another by multiplication by a unit. So it was very
important to know the group of units in those algebraic number
fields.)

A summary of what happens is that the group of units in the
ring of integers in an algebraic number field  F  is a
finitely-generated abelian group, (that's not obvious!) hence (easy)
it's isomorphic to a finite group  T  times a free abelian group  Z^r .
The finite subgroup  T  is (easy) the group of roots of unity that
lie in the field, and that' not usually hard to determine; at worst
you have to try factoring a finite list of cyclotomic polynomials
like  x^n - 1  over the field. The torsion-free part can be shown
to be of rank  s1+s2  where  s1  is the number of embeddings of the
field into the real numbers, and  s2  is the number of complex-conjugate
pairs of non-real embeddings. (These numbers make s1 + 2 s2 = [ F : Q ] .)
The calculation of this value of  r  is a little bit clever but not
hard to follow. The hardest part of all is to actually compute a set
of  r  generators of this group; typically one can find a set of  r  
independent units, i.e. one can find a group of units which is of
finite index in the full group of units, but then you have to decide
whether for example any simple combination of the units you know is
the square of another unit you didn't previously know about.

I like the book Number Theory by Borevich and Shafarevich (despite its
numerous misprints and lousy index) because it treats all these topics.
Definitely one to add to your bookshelf.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board