Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

A Guide to Arithmetic
Robin Chapman
August 5, 1994
These notes give a very brief resum´ of my number theory course
...
Any suggestions for improvements will be gratefully received
...


1

Basic notions

In number theory we deal with the set of natural numbers
N = {1, 2, 3,
...
, −2, −1, 0, 1, 2, 3,
...

We say that an integer m divides an integer n, or that n is divisible by m, or
that m is a factor or divisor of n, if there exists an integer r with n = rm
...
We write m | n if m divides n and m n
if m doesn’t divide n
...
2
Once we have the concept of divisibility we can define the notion of primality
...
If n > 1 and n isn’t prime then we say n is
composite
...
, pr are primes
...
2

1

2
2
...
If a,
b and m are integers, we say that a is congruent to b modulo m or write
a≡b

(mod m)

if m | (b − a)
...
)
For a fixed number m the relation of congruence is an equivalence relation
...

(ii) If a ≡ b (mod m) then b ≡ a (mod m)
...
2
Also congruence respects addition, subtraction and multiplication
...
2
Division in general not respected
...

Proposition
(i) If a ≡ b (mod m) and d | m then a ≡ b (mod d)
...
Then a ≡ b (mod m) if and only if as ≡ bs (mod ms)
...
We sometimes denote the
residue class containing a by a so that
a = {a + rm : r ∈ Z} = {
...

If m > 0 then there are exactly m residue classes modulo m
...
In particular if m > 0 then
the set S = {0, 1,
...

Another important example when m > 0 is
S = {a : −m/2 < a ≤ m/2}
...
, n − 1, n} and if m = 2n is
even then S = {−n + 1, −n + 2,
...

If we have a congruence modulo m involving an indeterminate x we can
ask if this congruence is soluble, and if so what the solutions are
...
This approach is
only efficient when m is small, and we shall seek better methods which are
practical for large m
...
2

Linear congruences

The most basic class of congruences are linear congruences, viz
...
By definition (1) is soluble if and only if m|(b − ax) for
some x, and this is true if and only if b − ax = my for some x and y
...
To investigate the solubility of linear congruences we must
answer the question: given integers a and m, which integers can be written
in the form ax + my with x, y ∈ Z? To solve this problem we need to recall
the notion of the gcd
...

(b) If g is the integer from part (a) then g = ar + bs for some r, s ∈ Z
...
It also follows that a number m has the form ax + by if and only
if g | m
...
We may suppose
that a and b are both positive
...
We repeat the following procedure until we get ak+1 = 0
...
When ak+1 = 0 then put g = ak , r = rk and s = sk
...

Returning to congruence (1), or equivalently equation (2), we see that it
is insoluble if g = gcd(a, m) b
...


(3)

Now if g = ar + ms then 1 = a r + m s ≡ a r (mod m)
...
Note that in general we get a solution modulo m , and this is equivalent to g different solutions modulo m
...
As this is quite a desirable state of affairs then we
introduce a piece of terminology; integers a and b are said to be coprime, or
a is coprime to b, if gcd(a, b) = 1
...
It easily
follows that if a is coprime to b and a ≡ a (mod b) then a is coprime to b
...

A useful property of coprime numbers is that their “least common multiple” is their product
...
2
3

Corollary Suppose that m and n are coprime
...
2
If p is a prime number then “most” numbers will be coprime to p
...

2
Corollary Let p be a prime
...
2
We can extend this by induction to products of more than two numbers
...
If p | a1 a2 · · · ak then p | ak for some j
...

Theorem (The Fundamental Theorem of Arithmetic) If n > 1 is a natural
number and
n = p 1 p 2 · · · p r = q1 q2 · · · qs
where the pi s and qj s are all prime, then r = s and we can re-order the qj s
such that pi = qi for all i
...

If we collect together occurrences of the same prime we can write
k

n=

p r1 p r2
1 2

· · · prk
k

r

pj j

=

(4)

j=1

where the pj s are distinct primes and each rj ≥ 1
...


2
...


(5)

The first congruence is equivalent to x = a+my so substituting in the second
gives
my ≡ b − a (mod n)
...
If g | (b−a) then this congruence has a unique solution
for y modulo n/g which translates into a unique solution for x modulo mn/g
...

Theorem The pair of congruences (5) have a simultaneous solution for x
if and only if g | (b − a) where g = gcd(m, n)
...
2
Corollary (The Chinese Remainder Theorem) If m and n are coprime then
the pair of congruences (5) has a unique solution modulo mn for any integers
a and b
...

If f (x) ≡ 0 (mod mn) is a congruence with m and n coprime we can solve the
same congruence modulo m and modulo n and then put the results together
to get the solution modulo mn
...
4

Euler’s ϕ-function

When p is prime then all numbers not divisible by p are coprime to p
...
We thus define ϕ(n) to be the number of a with 1 ≤ a ≤ n
which are coprime to n
...

The function ϕ is called Euler’s phi-function
...
In fact we can easily generalize this result
...
A number a is coprime to pr if and
only if a is coprime to p
...
Then ϕ(pr ) = pr−1 (p − 1)
...
To find the value in general we need to know how ϕ(mn) depends on
ϕ(m) and ϕ(n) whenever m and n are coprime
...

Proposition Let m and n be coprime natural numbers
...
2
Using this result and the Chinese Remainder Theorem we can now prove
the following theorem
...
Then ϕ(mn) =
ϕ(m)ϕ(n)
...


2
The main application of the phi-function is to the following result
...
Then
aϕ(n) ≡ 1 (mod n)
...


(b) If p is prime and a ∈ Z then
ap ≡ a

(mod b)
...
then eventually we reach one, viz
...
However we may find that we reach
5

a power ah with ah ≡ 1 (mod n) earlier
...
It is clear that
h ≤ ϕ(n), but in fact more is true
...
Then ar ≡ as (mod n) if
and only if r ≡ s (mod h)
...
Then h | ϕ(n)
...

This is equivalent to saying that every b which is coprime to n is congruent
to a power of a modulo n
...


2
...
This is
the problem of determining whether a specified number n is prime
...
However as n gets bigger this method becomes impractical
...

Fermat’s theorem implies that if n a and an−1 ≡ 1 (mod n) then n
cannot be prime
...
So as a basic primality test we pick a number a (usually a = 2
will work) and compute an−1 modulo n
...

This test avoids a vast amount of trial division but instead seems to
rely on the computation of an−1 which may be a really vast number! This
difficulty is more apparent than real, as we only need to find the value of
this modulo n
...
This
requires about n operations which is worse than trial division
...

The “binary trick” is an efficient algorithm for finding the value of ar
modulo n
...
Alas nature is not usually kind enough to
provide such an r but we can easily get around this
...
Then r1 = 1 and rk = r, if r has k binary digits,
and for each j either rj+1 = 2rj or rj+1 = 2rj + 1
...
, k successively as follows; ar1 = a, and if arj ≡ b (mod n)
then we compute arj+1 ≡ b2 or b2 a (mod n) according to whether rj+1 = 2rj
or 2rj + 1
...
If n is composite and an−1 ≡ 1
(mod n) we say that n is a pseudoprime to the base a
...
We now ask a more
6

modest question; given a composite number n, is there a base to which it is
not a pseudoprime? The following lemma says the answer is affirmative
...
2
Alas on further reflection we see that this result is very weak
...
We thus ask if n
is composite is there an a coprime to n such that n is not a pseudoprime to
the base a? The answer is no, for if n = 561 we find that a560 ≡ 1 (mod 561)
for all a coprime to 561
...
There has recently
been a major breakthrough in the theory of Carmichael numbers
...
2
This result is unfortunate for our primality test, as repeatedly testing a
Carmichael number for primality is practically certain to fail
...
6

General congruences and primitive roots

We now return to the general theory of congruences
...
If m
divides all the aj then the congruence reduces to 0 ≡ 0 (mod m) and we
call the congruence trivial
...
In this case we can ignore terms of higher degree than
xd and we say that the congruence has degree d modulo m
...
We know that an equation
of degree d over the real or complex numbers has at most d solutions
...
Fortunately this does not happen when m is
prime
...
This congruence cannot have more than d
distinct solutions modulo p
...

2
As with equations over the real numbers a congruence modulo p may have
fewer than d solutions
...

Proposition Let p be a prime
...
2
We draw two corollaries from this which we will use in the quest for a
primitive root modulo p
...
Then there are
exactly m distinct solutions of xm ≡ 1 (mod p) modulo p
...

Then there are exactly q r−1 (q − 1) distinct numbers of order q r modulo p
...

Lemma If a and b have orders h and k respectively modulo m, and h and k
are coprime, then ab has order hk modulo m
...
e
...
2
We can use the existence of a primitive root g modulo a prime p to simplify
many arguments
...
There is
also a nice procedure for recognizing primitive roots
...
, qr , then g is a primitive root modulo p if and only if
q (p−1)/qj ≡ 1 (mod p) for each j
...
If g is a primitive root of the prime p and a ≡ g r (mod p)
then we call r the discrete logarithm of a to the base g modulo p, and denote
r = logp,g (a)
...
We have the important formula
logp,g (ab) ≡ logp,g (a) + logp,g (b)

2
...


The Miller-Rabin test

We have observed that if p is prime then the only solutions to x2 ≡ 1 (mod p)
are x ≡ ±1 (mod p)
...
We can apply this result to primality testing
...
If the basic primality test fails on n for some base
r
a, i
...
, an−1 ≡ 1 (mod n) we consider the values of as , a2s , a4s ,
...
If this happens we conclude
that n is composite
...
One can show (but we won’t) the following result
...
2
This result shows that there is no analogue for the Miller-Rabin test
of Carmichael numbers
...
Repeating this k times one has at most
a 1/4k chance of failure
...


2
...
The RSA cryptosystem (Rivest, Shamir, Adleman,
8

1978) is the most famous example
...
One takes large
primes p and q (usually large, 100+ digits) and selects a number r coprime
to ϕ(pq) = (p − 1)(q − 1)
...

One publishes n = pq and r, but keeps p, q and s secret
...
Now it’s
easy to show that m s ≡ mrs ≡ m (mod n), so that possession of the key s
enables one to decode the message
...
As factorizing large numbers into primes is still an intractable
problem (but one on which progress is being made) the RSA system is secure
...
9

Mersenne numbers

There are certain classes of numbers which can be tested for primality by
special methods
...
One easily shows that if n is composite then Mn is also, so for Mn to
be prime it is necessary that n be prime
...
Nevertheless there is a test for primality of Mersenne
numbers which has given a series of numbers each of which has been the
highest known prime
...

Most Mersenne numbers of the form Mp with p prime are alas composite
...

Proposition If q is a prime factor of Mp = 2p − 1 where p is prime, then
q ≡ 1 (mod p)
...
We confine
ourselves to a prime modulus p, which we shall assume is odd
...

(†)
If p | a then (†) is equivalent to x ≡ 0 (mod p)
...
As (†) cannot have more than two distinct solutions modulo p then
these are the only solutions
...
If the congruence (†) is insoluble then a is
called a quadratic non-residue modulo p
...
If p is an odd prime and

9

a ∈ Z we define the Legendre symbol
a
p
Note that

a
p


 0


if p | a,
= +1 if a is a quadratic residue modulo p,


−1 if a is a quadratic non-residue modulo p
...
By our previous remarks we

see that the congruence (†) has precisely 1 + a distinct solutions modulo p
...
If g is a
primitive root modulo p then it’s easy to see that g s is a quadratic residue
modulo p if and only if s is even
...
Hence there are (p−1)/2 distinct quadratic
residues and (p − 1)/2 distinct quadratic non-residues modulo p
...

Proposition (Euler’s Criterion) If p is an odd prime and a ∈ Z then
a
p

≡ a(p−1)/2

(mod p)
...
Then
ab
p

=

a
p

b

...


2
To calculate further values of the Legendre symbol we use the following
result which is derived from Euler’s criterion
...

Put p = (p−1)/2 and define c1 , c2 ,
...

Let µ be the number of negative cj s
...


2
By turning the handle we get the following important corollary
...
Then
2
p
and

−2
p

=

=

+1 if p ≡ 1 or 7 (mod 8),
−1 if p ≡ 3 or 5 (mod 8),
+1 if p ≡ 1 or 3 (mod 8),
−1 if p ≡ 5 or 7 (mod 8)
...
Alas the work involved steadily increases
...
This result,
conjectured by Legendre, and proved by Gauss is the celebrated Law of
Quadratic Reciprocity
...

Theorem (Law of Quadratic Reciprocity) Let p and q be distinct odd primes
...

p

2
Using this result the practical computation of Legendre symbols is now
straightforward
...
1

Diophantine equations
Sums of squares

We now turn to the subject of sums of squares
...
Note that we admit 0 = 02 as a square
...
If we consider the numbers from 1 to 100 we
find 10 of them are squares, 43 are sums of two squares, 86 are sums of three
squares, and all are sums of four squares
...

It is easy to see that if n ≡ 3 (mod 4) then n is not the sum of two
squares, and if n ≡ 7 (mod 8) then n is not the sum of three squares
...
The
following result gives a further restriction on which numbers are sums of two
squares
...
2
Corollary If n = x2 + y 2 then n = r2 m where m is a sum of two squares
which is divisible by no prime p satisfying p ≡ 3 (mod 4)
...
If
we consider the numbers n up to 100 we find that if n satisfies this condition,
then n is the sum of two squares
...
In order to show that the answer
is yes we need the following useful lemma
...
2
It now suffices to show that any prime p which is not congruent to 3
modulo 4 is a sum of two squares
...

Theorem If p is a prime number with p ≡ 1 (mod 4), then p is a sum of two
squares
...

Theorem Let n ∈ N have the prime factorization
r

pj j
...
2
Another nice result is that a prime p ≡ 1 (mod 4) can be expressed as
the sum of two squares in a unique fashion
...
2
In general one can work out a formula giving the number of representations of a number n as the sum of two squares, but we shall not go into
this
...
It is
possible for numbers m and n to be sums of three squares, yet for mn not to
be
...
We just state the main result
...
2
The proof of one half of the theorem is easy, namely that a number
n = 4a m with m ≡ 7 (mod 8) is not the sum of three squares
...

When we come to sums of four squares life becomes easier again
...
Again we have a product rule
...
2
This enables us to reduce the proof of the following theorem to the case
where n is prime
...
2

4
...

We wish to find integer solutions to this equation
...
We have the obvious solution
(x, y) = (1, 0) so it suffices to consider the case where x, y ∈ N, and such
solutions are called non-trivial
...

12

Lemma If n is a square then Pell’s equation x2 − ny 2 = 1 has no non-trivial
solution
...

Before showing how to find a solution, we show that given one solution we
can find infinitely many others
...
2
Corollary If x2 − ny 2 = 1 has a non-trivial solution, then it has infinitely
many solutions
...
This shows that (x/y)2 is√
close to n and so the rational number x/y is
√
close to the irrational number n
...
It follows that to solve Pell’s equation
√
one must find very good rational approximations to n
...

To approximate a real number ξ by rationals we use the technique of
continued fractions
...


...
For convenience we abbreviate
this expression by a0 , a1 ,
...
We can represent any rational number by
a continued fraction, and approximate any irrational number by continued
fractions by the following procedure
...
Let [ ξ ] denote the integer part of ξ,
i
...
, the integer a such that a ≤ ξ < a + 1
...

If η0 = 0 then ξ = a0 = a0 ∈ Q and we stop, otherwise we put ξ1 = 1/η0 ,
a1 = [ ξ1 ] and η1 = ξ1 − a1
...

If ξ ∈ Q we eventually get ηr = 0 and so ξ = a0 , a1 ,
...
, ar ,
...

are the numbers c0 , c1 , c2 ,
...
, aj
...
We can obtain the convergents easily by a recurrence
relation
...
be the convergents to the continued fraction
a0 , a1 , a2 ,
...
2
√
If we apply the continued fraction technique to n we see that we get a
recurring continued fraction
...

Theorem Let n ∈ N be a non-square
...
, am−1 , 2a0 , a1 , a2
...
e
...

Also if the cj are the convergents of this continued fraction and cj = hj /kj
in lowest terms, then
2
sm
h2
sm−1 − nksm−1 = (−1)

for all s ∈ N
...
However if m is odd then we get a solution
of the negative Pell equation x2 − ny 2 = −1 before we get a solution of Pell
...

Lemma If x2 − ny 2 = −1 then x 2 − ny 2 = 1 where x = x2 + ny 2 and
y = 2xy

---