### your ad here sells all year

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.

## Leave a Comment