## 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

]