## Archive for April, 2014

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!)*

i’m going to SPACE next week.

it’s columbus ohio, so the list

narrows down pretty quick:

the “arnold classic”, SPACE,

and, um, let’s see… there

*must* have been something

else…

“ameriflora”, maybe, in your

dreams. “miracle mile”, back

from the “miracle” days of

the long-gone late-great

thriving american working class

that shopped (until it dropped)

there. no. never mind.

the chief attraction of columbus

for *me* is that this is where

i *am* (moving around… or

even moving *stuff* around…

is *much* harder than they’d

have you believe…; & of course

the *next* best thing about

columbus is that *madeline*

lives here (and our happy home

*is* our happy home, much to

my surprise). and *staying*

here keeps me this way (happy).

it’s (1) cold (2) cruel

world (3) out there.

the (very existence of)

the billy ireland museum is,

enough to put columbus *somewhere* on

the comics “map”… and there’s already

a better list of local-and-quasi-nearby

talent at the “space” site… so let

me just give a shout-out to ray (!!) t

and “max ink” (still working as far as

i know); one more for glen brewer (even

though i think glen has quit the scene;

his _askari_hodari_ was, for me, very

much a local highlight).

everybody knows about _bone_;

it won’t escape my notice here

that the astonishing paul hornschemeier

lived here, too, when he was getting

started and i met him (and he drew

a cover for my zine gratis… eat

your hearts out). in fact, ghod

*bless* columbus. good night.