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.
the livingston review 