|
|
| Author |
Message |
| 25 new of 81 responses total. |
aruba
|
|
response 25 of 81:
| 
May 18 05:12 UTC 2002 |
Well, I guess you have to know what a ring is to make sense of them.
|
gelinas
|
|
response 26 of 81:
|
May 18 06:37 UTC 2002 |
That, and the notation.
|
utv
|
|
response 27 of 81:
|
May 18 18:54 UTC 2002 |
what we need is One Ring to explain it all...
|
aruba
|
|
response 28 of 81:
|
May 18 19:36 UTC 2002 |
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.
|
jp2
|
|
response 29 of 81:
|
May 18 19:58 UTC 2002 |
This response has been erased.
|
gelinas
|
|
response 30 of 81:
|
May 19 03:25 UTC 2002 |
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.
|
aruba
|
|
response 31 of 81:
|
May 19 04:43 UTC 2002 |
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.
|
jp2
|
|
response 32 of 81:
|
May 19 16:40 UTC 2002 |
This response has been erased.
|
flem
|
|
response 33 of 81:
|
May 20 15:46 UTC 2002 |
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.
|
aruba
|
|
response 34 of 81:
|
May 20 21:51 UTC 2002 |
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.
|
remmers
|
|
response 35 of 81:
|
May 21 16:28 UTC 2002 |
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.)
|
remmers
|
|
response 36 of 81:
|
May 21 16:31 UTC 2002 |
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 "...")
|
jp2
|
|
response 37 of 81:
|
May 21 17:12 UTC 2002 |
This response has been erased.
|
flem
|
|
response 38 of 81:
|
May 21 17:12 UTC 2002 |
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.
|
rcurl
|
|
response 39 of 81:
|
May 21 18:41 UTC 2002 |
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).
|
flem
|
|
response 40 of 81:
|
May 21 18:49 UTC 2002 |
I think the result I posted for proof has applications to cryptography,
which I may explore if I get more turns. But in general, I don't bother
to apply math to the Real World, it's just for my amusement and mental
exercise.
|
remmers
|
|
response 41 of 81:
|
May 21 20:51 UTC 2002 |
Oops, I mean to say "the sum of the absolute values" of the
numerator and denominator, not "the absolute value of the sum".
|
remmers
|
|
response 42 of 81:
|
May 21 20:51 UTC 2002 |
(My #41 was Re: #38)
|
aruba
|
|
response 43 of 81:
|
May 21 21:13 UTC 2002 |
Nice job John - with the correction in #41, I'll accept that proof. You're
up.
|
remmers
|
|
response 44 of 81:
|
May 21 22:41 UTC 2002 |
Okay, thanks. I'll come up with a new poser tomorrow.
|
remmers
|
|
response 45 of 81:
|
May 22 12:00 UTC 2002 |
New problem:
One leg of an L-shaped hallway is w1 feet wide; the other leg
is w2 feet wide. What is the length of the longest ladder
that can be carried horizontally around the corner?
|
jp2
|
|
response 46 of 81:
|
May 22 15:40 UTC 2002 |
This response has been erased.
|
aruba
|
|
response 47 of 81:
|
May 22 16:41 UTC 2002 |
Nope.
|
mdw
|
|
response 48 of 81:
|
May 23 00:31 UTC 2002 |
How tall is the ceiling? How wide are the rungs on the ladder?
|
janc
|
|
response 49 of 81:
|
May 23 03:48 UTC 2002 |
He said "carried horizontally".
A X
+--------------------
| /
| /
| / w1
| /________________
| /|B
| / |
|/ |
Y | |
w2
What's the maximum length a ladder can be if it is jammed in the corner
at a particular angle? Let's let t be the angle AYB in the diagram
above. The length of segment YB is w2*sin(t) and the length of BX is
w1*cos(t). So the maximum ladder length at this angle is
L(t) = w1*cos(t) + w2*sin(t) 0 < t < pi/2
Now, we want to take the derivative of this and set it to zero, to find
the angle at which the length of the ladder is at a minimum. We plug
that result back into the formula above to get the ladder length at that
angle.
Now I'm starting to get into trouble, because every math book I own is
still packed, and I haven't done any calculus or much algebra with
trigonometric functions for 20 years or so.
I think
d L(t) / dt = - w1 * sin(t) + w2 * cos(t)
Setting that to zero and solving gives
tan(t) = w2/w1
If that's true, I suppose
sin(t) = w2/sqrt(w1^2 + w2^2)
cos(t) = w1/sqrt(w1^2 + w2^2)
plugging those into the L(t) formula gives:
w1*w1/sqrt(w1^2 + w2^2) + w2*w2/sqrt(w1^2 + w2^2)
which simplifies to sqrt(w1^2 + w2^2)
which is wrong. That's the length of line AB which is way too short.
OK, I see I misremembered some trig and got the L(t) formula wrong. It
should have been:
L(t) = w1/cos(t) + w2/sin(t) 0 < t < pi/2
I've forgotten what the reciprocals of sin() and cos() are called, much
less what their derivatives are. So I'm going to abandon this to
someone with a better memory or a better idea.
Darn - the question Mark asked was for my two favorite proofs of all
time. I could have done that one in my sleep.
|