wordpress *won’t* let me publish my copy! quitting forever again soon i bet! dammit!!!!

February 23, 2014 in Job, Number Theory

[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).

Advertisement