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.

Advertisements



    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s



%d bloggers like this: