Archive for the ‘Number Theory’ Category

6.1.5
Let a, b, c, & d
be integers satisfying
b > 0, d > 0, and
ad – bc = 1.
Let n = max{b,d}.
Then a/b and c/d are consecutive
fractions in the n^th Farey Sequence.

Proof:
Since ad-bc=1, we have
ad/(bd) = (1+bc)/(bd), hence
a/b = 1/(bd) + c/d and so
a/b > c/d.

Note that (cf. Corollary 6.2)
ad-bc = 1 also implies
(a,b) = 1 and (c,d) = 1;
our fractions are in
“lowest terms” (and hence
appear in F_n).

Now suppose c/d & a/b are *not* adjacent.
Then there is at least one fraction,
which we may assume is in “lowest terms”,
“p/q”, say, with (p,q) = 1, such that
p/q is *between* c/d and a/b
in the Farey sequence F_n:
F_n = { …, c/d, …, p/q, …, a/b, …}.

Then
q = (ad-bc)q
= adq ___________ – bqc
= adq – bdp + bdp – bcq
= d(aq-bp) + b(dp-cq)
(*).

But a/b > p/q implies
aq – pb > 0, and so
(since the variables are integers)
we have that
aq – bp is greater-or-equal to 1
(aq – bp \ge 1).
The same computation with different
letters shows that
[p/q > c/d] \implies [dp – cq \ge 1].

These inequalities together with (*) give
q = d(aq-bp) + b(dp-cq)
q \ge d + b.

Recall that n = max{b,d}.
It follows that d + b > n.
This gives us q > n, a contradiction
(“p/q” cannot be in F_n with q > n).

Hence a/b and c/d *are* adjacent in F_n; done.

3.2.4
Let (n, p) denote an integer and a prime #;
is “x^2 == n (mod p)” solvable for the given
pairs (n, p)?
a. (5, 227) NO
b. (5, 229) YES
c.(-5, 227) YES
d.(-5, 229) YES
e. (7,1009) YES
f.(-7,1009) YES
(The calculations are routine.)

3.2.6
With a TI “grapher”, I’ve just found that
139^2 == 150 (mod 1009).
One simply puts
Y_1 = 1009(fPart(X^2/1009))…
this computes equivalence-classes-mod-1009
of the squares of each of the inputs successively…
and “scrolls down” in the TABLE window
(set to display natural number X-values).

Hence x^2 == 150 (mod 1009)
*does* have a solution.
(In fact, two of them; the other is of course
870 (= 1009 – 139)).

In detail,
139^2 = 19321 = 19*1009 + 150
and
870^2 = 756900 = 750*1009 + 150.
(The point here is that one may easily
*verify* such results by “paper-&-pencil”
methods.)

To find the roots *entirely* by p-&-p methods,
the best line of attack would probably be via
“primitive roots”.

3.2.7
We seek primes p such that x^2 == 13 (mod p)
has a solution.

The case of p = 2 (“the oddest case of all”)
reduces to x^2 == 1 (mod 2); of course this
*does* have a solution. (So we add “2” to our
list of primes.)

In the case of p = 13, our equivalence is x^2 == 0;
again, this clearly *does* have a solution (and “13”
belongs in our list).

Finally, let p be an odd prime with p \not= 13.
The Gaussian Reciprocity Law now gives us that
(13|p) = (p|13)
(where (_|_) denotes the Legendre symbol).
[Remark:
This happens “because 13 == 1 (mod 4)”…
recall that (p|q) and (q|p) have opposite
signs only when *both* primes are in “4k+3”
form.]

So we need only check the equivalence classes (mod 13)
for “perfect squares”. We know from earlier work that
there are *six* perfect squares (mod 13).
1, 4, and 9 are the “obvious” ones…
4^2 = 16 == 3…
by suchlike computations, one easily arrives at
{1, 4, 9, 3, 12, 10} =
{1, 3, 4, 9, 10, 12};
any odd prime p different from 13 must be
congruent-modulo-13 to one of these “perfect
squares mod 13”.

Summarizing: x^2 == 13 (mod p)
has solutions for p = 2, for p = 13,
and for
p \in { 13k + r |
k \in N ,
r \in {1, 3, 4, 9, 10, 12}
}.
(*)
**************************(end of exercise)******

[
Remark:
Our “list” of primes now begins
L = {2, 3, 13, 17, 23, …}
.
(Some students had {2, 3, 13})
.
It can be shown
(using “Dirichlet’s Theorem on Primes
in Arithmetic Progressions” [DT], section 8.4)
that there are *infinitely many* prime numbers
“for each r” in (*) (i.e., in each of the
“perfect square” equivalence classes mod-13)
.
One is of course not expected to know
about DT already (or to learn it now).
But questions like

*is* there a prime that’s congruent to 4 (mod 13)?

arise in the present context in a very natural way:
it so happens that 17 == 4 (mod 13), and so
in “testing primes” (in their natural order
2, 3, 5, … , 13, 17, …) one soon learns
the answer: there *are* such primes.
(But then… how *many*? And so on.)
]

4.1.2
Clearly with
2^k || 100! and 5^r || 100!,
one has r < k, and so
to "count zeros at the right
end" of Z = 100! we need only
compute "r"
(the largest power of *10* dividing Z…
the number of zeros in question…
is clearly the same as the largest
power of *5* dividing Z).

But for this we need only consult
de Polignac's formula (Theorem 4.2):
r = [100/5] + [100/25] + [100/125] + …
r = 24.

4.1.9
Let BC(x,y) denote the Binomial Coefficient
BC(x,y) = x!/[y!(x-y)!]
(one usually pronounces this object
"x choose y"; see Section 1.4).

One then has the familiar "Pascal's Triangle"
property: a given "entry" can be computed
by "adding the two entries above it".
The object of study in this exercise is then
the "middle entry" of an "even numbered row";
simple algebra gives us

(2n)!/(n!)^2 =
BC(2n, n) =
BC(2n-1, n-1) + BC(2n-1, n) =
2BC(2n-1, n-1).

This is clearly an even integer.

6.
With a TI “grapher”, I’ve just found that
244^2 == 5 (mod 1009). One simply puts
Y_1 = 1009(fPart(X^2/1009))…
this computes the equivalence-class-mod-1009
of the square of each input successively…
and “scrolls down” in the TABLE window
(set to display natural number X’s).

Hence x^2 == 5 (mod 1009) *does* have a solution.
(In fact, two of them; the other is of course
765 (= 1009 – 244)).

In detail,
244^2 = 58536 = 59*1009 + 5
and
765^2 = 585225 =580*1009 + 5.
(The point here is that one may easily
*verify* such results by “paper-&-pencil”
methods.)

To find the roots *entirely* by p-&-p methods,
the best line of attack would probably be via
“primitive roots”.

trouble is, is, that that “5”
was supposed to’ve been “150”.
once more, dear friends!
(or close the wall up with our
english dead!)

[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
]