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

]