Archive for February, 2014
[link of the hour:
number theory and physics.]
********************************************
Define f(n) = n – \phi(n).
Then f is the function that, from
CRS(n)={0,1,…,n-1}
(a Complete Residue System (mod n)),
counts the elements “a”
such that (a,n) \not= 1.
We can think of this as counting
the objects of the set
ZD(n):= CRS(n) \setdifference RRS(n):
f(n) = #ZD(n).
(Objects of ZD(n) are sometimes called
“zero divisors” (mod n).)
Now if x \in ZD(d), we have (x,d) \not= 1
and so (recall d|n) we get (x,n) \not= 1 as well:
x \in ZD(n). Thus ZD(d) \subset ZD(n).
But then f(d) \le f(n),
or, in other words,
n – \phi(n) \ge d – \phi(d).
This is *almost* what we want…
the “\ge” (“is greater than or equal to”)
must be “made strict”… we must
*eliminate* the possibility that
the two sides of our equation are equal.
So notice that
d \not== 0 (mod n)
whereas
d == 1 (mod d).
Thus [0] and [d] represent
*different* objects (equivalence classes)
in ZD(n) but represent the *same* object
in ZD(d). It follows that the “\subset”
relation found three paragraphs above
is *strict*; our result follows:
n – \phi(n) > d – \phi(d).
today’s writing project.
i played guitar (and even talked a little)
in church today, too, so it’s been
a pretty productive day for a sunday.
(i suppose. now that i think about it,
monday morning deadlines have led me
to many a *highly* productive sunday
here at the grading table. and grading
is the actual *work*…)
********************************************
Let f(x) = x^3 + x + 57.
(Find all x s.t.
f(x)\equiv 0 (mod 125).
)
Since 125=5^3, we begin by working “mod 5”:
f(0) = 57 == 2
f(1) = 59 == 4
f(2) = 67 == 2
f(3) = 87 == 4
f(4) == f(-1) == 50 == 0 (mod 5).
So f has exactly one “mod-5 root”
(namely 4) and we consider
f'(4) = 3(4)^2 + 5 = 21 == 1 \not == 0 (mod 5).
This means that 4 is a *non-singular* root.
Hensel’s Lemma (HL)
now tells us that there is
exactly one root of f (mod 125).
But now, since
f(4) = 4^3 + 4 + 57 = 125,
we are done:
x=4
is the *only* solution to f(x)==0 (mod 125).
*************************************************
Let g(x) = x^3 + 10x^2 + x + 3.
(Find all x s.t.
g(x)\equiv 0 (mod 27).
)
Since 27=3^3, we begin by working “mod 3”:
g(0)==0
g(1)==0
g(2)==2 (mod 3).
Next, we’ll compute g'(x) = 3x^2 + 20x + 1
and evaluate it at each of our “mod 3” roots:
g'(0) =1 and g'(1) = 24 == 0 (mod 3).
The root at 1 is *singular*
(so “HL” isn’t helpful).
If “1” were lifted to a mod-9 root, x,
we would have x \in {1 +k*3} = {1, 4, 7}.
But
g(1) = 15 == 6,
g(4) = 231 == 1, and
g(7) = 843 == 6 (mod 9),
so there is *no* mod-9 root of f
satisfying x == 1 (mod 3)
(and so certainly no such mod-27 root).
The root at 0 is *non*-singular.
Since g'(0) = 1, its “mod-3 inverse” is
\bar{g'(0)} = 1.
“Plugging in” on “Hensel’s Formula”
(we have a_j = a_1 = a = 0;
our “f” is called “g”)
a_{j+1} = a_j – f(a_j)\bar{f'(a)}
(Display 2.6 of [NZM]) gives us
a_2 = 0 – 3(1) == -3 == 6 (mod 9).
Repeating the process,
a_3 = a_2 – g(a_2)\bar{g'(a)}
a_3 = 6 – 585(1)
a_3 = -579
a_3 = -(21*27 + 12).
a_3 == -12 == 15 (mod 27).
Our one-and-only solution
to f(x)==0 (mod 27) is x = 15.
(The result checks readily
[a calculator is helpful]:
f(15) = 5643 = 209*27 == 0 (mod 27).)
*************************************************
Let p be an odd prime.
Let L = (1^2)(3^2)…([p-1]^2) and
let R = (-1)^{(p+1}/2}.
We will show that L = R (mod p).
Note that for 1 \le k < p
("\le" denotes is-less-than-or-equal-to)
we have k = -(p-k) (mod p).
Rearranging the factors of L gives
L=1(-1)(p-1)2(-1)(p-2)…(p-2)(-1)(2).
L=(-1)^{(p-1)/1}1*2*3*…*(p-1).
Since 1*2*…*(p-1) = (p-1)!, we can
apply Wilson's Theorem:
L\equiv (-1)^{(p-1)/2}*(-1) (mod p).
But then L = R as we were to show.
One may now derive
(2^2)(4^2)…([p-1]^2) \equiv R
by squaring "Wilson's Equation"
[(p-1)!]^2 \equiv (-1)^2 (mod p).
Note that (-1)^2 = 1 = (-1)^{p-1}:
[(p-1)!]^2 \equiv(-1)^{p-1} (mod p).
Divide on the left by L;
divide on the right by R.
The result follows.
(Division "works" because p
is a prime… we can always
"cancel" factors less than p
in this case.)
(One should *not*… if instructed
to prove *two* equivalences…
simply remark that the second
"is similar to" the first:
if our textbook authors hadn't
wanted at least *some* details,
they presumably would not have
asked that part of the question
at all.)
(n!+1, (n+1)!+1)=1. [For all n \in N.]
[Let n \in N.]
Suppose (n!+1, (n+1)!+1) = K > 1.
Then K has a prime divisor p>1.
We have p|(n!+1) and p|(n+1)!+1.
Since “p|x and p|y” implies that
“p|(y-x)” in all cases, we have
p|[ (n+1)!+1 – (n!+1) ]
p|[ (n+1)n! – n!]
p|n*n!.
But then (because p is prime) p|n!.
This is absurd since we also know p|n!+1.
No such p exists; K = 1; we are done.
[
i’ve been cranking out *lots* of number
theory problems… i’ve never taught the
subject at this level of detail and *need*
to do lots of problems (in order that
exercises like this can *become* “routine”.)
but i’ve only *typed up* a few (one
problem set [out of four that i’ve marked
so far]). anyhow, none of the class
had a proof this short-&-sweet so here
it is now for my loyal subscribers.
this is a *great* quarter so far.
getting back to work.
oops, “semester” so far.
\bye
]
the livingston review 