This item text has been erased.

81 responses total.

Then there is a y such that xy = 1.

This response has been erased.

What is y !? I know its not factorial. 

y = 1/x ... isn't that enough?

Re: #3
"y != 0" is "y is not equal to zero".  The usual "not equal" symbol is
much harder to do consistently across computer platforms.

x and y are either both irrational or both rational.

if x and y are mail parcels, they are both irradiated.

This response has been erased.

xyy < normal

Either xyx < 1 or yxy < 1 

This response has been erased.

Kind of obvious, I would have thought.

This response has been erased.

Okay, then let's try a different game.

The person who's "it" posts a mathematical fact.  The first person
to supply a proof acceptable to the poster is now "it" and gets to
enter the next fact.

In the interest of keeping the game moving and also keeping it
interesting, the facts should be neither too trivial nor too
difficult to prove.  In particular, avoid unsolved conjectures.

I'll start:  Prove that there are infinitely many prime numbers.

This response has been erased.

I'll accept that.  Go!

This response has been erased.

Hmm.  I believe integers modulo, say, 5 will do.  ISTR that integers modulo
any prime will do, but don't recall how to go about proving it.  w.r.t.
integers mod 5, it suffices to observe that 3 = 4 * 2 mod 5.  

This response has been erased.

Yeah, but I couldn't remember the exact definition of prime within a ring,
so I went for an example that I thought would work with a weaker definition.
My turn, hm?  Well, what the heck, let's generalize:  

Definitions:

An element of a ring is a unit if it has a multiplicative inverse. 

An element p of a ring is prime if it is not a unit and if it cannot
be decomposed into factors p = ab, where neither a nor b is a unit. 

Claim:  Let p be a positive prime integer.  Then the ring Z/pZ (integers 
modulo p) contains no prime elements.  

(I'm not entirely happy with these definitions and this statement of 
the claim, but I don't have my books with me and that's the best I can 
do in ten minutes on the internet.  Feel free to improve.)

Hungerford says:

An element c of a ring R is *irreducible* if
    (i) c is a nonzero nonunit
    (ii) c = ab ==> a or b is a unit.

An element p of a ring R is *prime* if
    (i) p is a nonzero nonunit
    (ii) p | ab ==> p|a or p|b.

In Z/pZ, primes and irreducibles are the same thing.  In a general domain
(a ring where ab = 0 ==> a=0 or b=0), primes are irreducible, but
irreducibles are not necessarily prime.

(As a side note, I first saw Red Dwarf about the time I learned that, and
for a long time, I heard the beginning of the theme song as,
        "It's cold outside, primes are irreducible"
Dunno why.)

My brain hurts. <sulks>  Truly, as a non-math person, I'm impressed.

Hungerford is a good book.  I used a library copy for a couple of months when
I was a research assistant.  I've wished a couple of times since then that
I owned a copy.  

didn't tolkien write THEbook on Ring Theory.

I found 19 and 20 completely incomprehensible.

Well, I guess you have to know what a ring is to make sense of them.

That, and the notation.

what we need is One Ring to explain it all...

Right, notation:

Z refers to the integers: { ..., -2, -1, 0, 1, 2, ... }
pZ refers to the multiples of p: { ..., -2p, -p, 0, p, 2p, ... }
Z/pZ is Z "modded out" by pZ.  There are a couple of ways to think about
that; the simplest is to think of identifying all integers with the
remainder you get when you divide them by p.  So Z/pZ can be thought of as
the set { 0, 1, ..., p-1 }.  To do addition, add two numbers as usual, then
take the remainder upon dividing by p.  Do multiplication similarly.

A ==> B is pronounced "A implies B", and is the same as saying "If A is
true, then B is true".

p|a is pronounced "p divides a".  That means there is an integer b such that
a = p*b.

A ring is basically a set on which you have defined addition and
multiplication.  THere are a few more conditions (there must be an additive
identity (called 0), a multiplicative identity (called 1), and each element
must have an additive inverse (so for each a, there must be an element -a
such that a + -a = 0)), but that's basically it.

This response has been erased.

I understand modulo, so Z/pZ makes sense, e'en if I usually think of that
operator as "divided by".  And the "implies" operator is one I've seen before,
e'en if I didn't recognise the context and applicability.  This is the first
I've seen the "divides" operator, though.

Thank you, Mark.

Lemma: If p is prime and 0 < a < p, then we can find b with 0 < b < p 
which is such that the remainder on dividing ab by p is 1.

Proof: Suppose b and c are integers with 0 <= b,c < p.  Then if ab and ac 
had the same remainder upon division by p, we'd have

ab = qp + r  for some q and r
ac = sp + r  for some s and the same r

==> ab - ac = qp - sp ==> a(b-c) = (q-s)p ==> p | a(b-c).  Since p is 
prime, that means either p|a or p|(b-c).  But p can't divide a, since 0 < 
a < p.  So p|(b-c).  And since b and c are between 0 and p, -p < b-c < p, 
and the only multiple of p in that interval is 0.  So b-c must be 0.  That 
is, b=c.

So it follows that the numbers 0, a, 2a, ..., (p-1)a all have distinct 
remainders when divided by p.  Of course there are only p possible 
remainders (0 through p-1), so by the pigeon-hole principle, each 
remainder is generated by some multiple of a.  In particular, there is 
some b such that ab has remainder 1 when divided by p.  If b were 0, ab 
would be 0, and not have remainder 1.  Therefore we're safe in saying 
that 0 < b < p.

-------

So it follows that if a is a nonzero element of Z/pZ, then there is 
another nonzero element b such that ab=1.  That is, all nonzero elements 
of Z/pZ have inverses; i.e., they're units.  (That's the same thing as 
saying that Z/pZ is a *field*.)  So Z/pZ has no nonzero nonunits; 
therefore it contains no primes.

You could generalize this theorem to say that if you start with any 
commutative ring and mod out by a prime ideal, you get a field.

This response has been erased.

Well done, Mark.  I spent much of the weekend with my nose in a textbook
trying to remember how to prove this myself.  My result was a bit more
notation-heavy, and hence a little shorter, but was essentially the same chain
of logic.  The book presented a discussion which included a proof of the
generalized theorem in #31, but was so heavily theoretical that distilling
it down to a direct proof for this case was difficult.  

OK, new problem.  A set is *countable* if it can be put into one-to-one
correspondence with the positive integers.  Show that the set of all
rational numbers is countable, but the set of all real numbers is not.

Let S[n] be the set of all rationals such that the absolute value of
the sum of the numerator and denominator (in lowest terms) is n,
for n = 1, 2, 3, etc.  Each S[n] is finite, and their union is the
set of all rational numbers.  Hence the rationals are countable.
(Hopefully you'll allow me to use without proof the fact that the
union of a sequence of finite sets is countable.)

For the second question, it suffices to prove that the set of reals
between 0 and 1 is uncountable.  I'll do this by contradiction.
Assume that the set is countable.  Then we can order it in sequence:
r[1], r[2], ..., r[n], ... .   Let d[k] be the k-th digit in the
decimal expansion of r[k] (k >= 1).  For each k, choose a digit
e[k] != d[k].  Then the number x = 0.e[1]e[2]...e[k] is not in the
sequence {r[n]}, contradicting the assumption.  Hence the reals
are uncountable.  

(There's a slight sloppiness in both of the above arguments that
needs fixing up, having to do with non-uniqueness of representation.
But I'm too lazy to do that at the moment.)

Oops, the x in the above is supposed to be an infinite decimal
expansion:  x = 0.e[1]e[2]...e[k]...
(I forgot the second "...")

This response has been erased.

I'm not sure I believe that S[n] is finite, as written.  S[1] would contain
-2/1, -3/2, -4/3, ..., unless I've misunderstood.  

How do any of you that understand these branches of number theory use
it for practical purposes? The closest it comes to the math I use
is in probability theory, and only on a few occasions have I wished
I knew it better. (Once was when a practical problem yielded an integral
equation whose solution was finite only at a subset of rational
numbers, but its moments were all simple, so I didn't worry about it).

- Backtalk version 1.3.30 - Copyright 1996-2006, Jan Wolter and Steve Weiss