4.4 Solving Congruences

Question 1

Linear Congruence:

Answer 1

A congruence of the form
ax ≡ b (mod m),
where m is a positive integer, a and b are integers, and x is a variable, is called a linear congruence.

Such congruences arise throughout number theory and its applications.

Question 2

Inverse of a modulo m:

Answer 2

Integer ~a such that
~aa ≡ 1 (mod m), if such an integer exists,
is said to be an inverse of a modulo m.

Question 3

Theroem 1:

About inverse of a modulo m, conditions for it.

Answer 3

If a and m are relatively prime integers and m > 1, then an inverse of a modulo m exists.
Furthermore, this inverse is unique modulo m. (That is, there is a unique positive integer a
less than m that is an inverse of a modulo m and every other inverse of a modulo m is congruent to a modulo m.)

Question 4

Proof of theorm 1:

Answer 4

By Theorem 6 of Section 4.3, because gcd(a, m) = 1, there are integers s and t such that
sa + tm = 1.
This implies that
sa + tm ≡ 1 (mod m).
Because tm ≡ 0 (mod m), it follows that
sa ≡ 1 (mod m).
Consequently, s is an inverse of a modulo m. That this inverse is unique modulo m is left as
Exercise 7.

Question 5

To find inverse of a modulo m:

Answer 5

To find this
inverse, we look for a multiple of a that exceeds a multiple of m by 1. For example, to find an
inverse of 3 modulo 7, we can find j ⋅ 3 for j = 1, 2, … , 6, stopping when we find a multiple of
3 that is one more than a multiple of 7. We can speed this approach up if we note that 2 ⋅ 3 ≡
−1 (mod 7). This means that (−2) ⋅ 3 ≡ 1 (mod 7). Hence, 5 ⋅ 3 ≡ 1 (mod 7), so 5 is an inverse
of 3 modulo 7.

Question 6

Example 3!!

Answer 6

What are the solutions of the linear congruence 3x ≡ 4 (mod 7)?
Solution: By Example 1 we know that −2 is an inverse of 3 modulo 7. Multiplying both sides
of the congruence by −2 shows that
−2 ⋅ 3x ≡ −2 ⋅ 4 (mod 7).
Because −6 ≡ 1 (mod 7) and −8 ≡ 6 (mod 7), it follows that if x is a solution, then x ≡ −8 ≡
6 (mod 7).

??

okay we make remainders positive.
and -6(x) = -8(mod 7)
where -6 = 1(mod)7 and -8 = 6(mod)7

Question 7

THE CHINESE REMAINDER THEOREM

Answer 7

Let m1, m2, … , mn be pairwise relatively
prime positive integers greater than one and a1, a2, … , an arbitrary integers. Then the system
x ≡ a1 (mod m1),
x ≡ a2 (mod m2),
⋅
⋅
⋅
x ≡ an (mod mn)
has a unique solution modulo m = m1m2 ⋯ mn. (That is, there is a solution x with
0 ≤ x < m, and all other solutions are congruent modulo m to this solution.)

Question 8

Proof of chineese remainder theorem:

Answer 8

OVER THE TOP OF HEADDDD : (
Page 294
m = m1.m2.....mn
Mk = m/mk   (k = 1,,,,n)
now, gcd(Mk,mk) = 1
=> Mkyk = 1 (mod mk)  - yk inverse exists.
now, x = a1M1y1 + . . + anMnyn

To show that x is simultaneous Soln:
Mj = 0 (mod Mk) (when j != k)
So, x = ak Mkyk = ak (mod mk)

for k = 1, 2, … , n. We have shown that x is a simultaneous solution to the n congruences.

Question 9

EXAMPLE 6!!

Answer 9

5t + 1 ≡ 2 (mod 6),
which can be solved to show that t ≡ 5 (mod 6) (as the reader should verify).!!???

inverse it is dude

30u + 26 ≡ 3 (mod 7).
Solving this congruence tells us that u ≡ 6 (mod 7) (as the reader should verify).!!!??

Question 10

Computer Arithmetic with Large numbers:

Answer 10

Suppose that m1, m2, … , mn are pairwise relatively prime moduli and let m be their product.
By the Chinese remainder theorem, we can show (see Exercise 28) that an integer a with 0 ≤
a < m can be uniquely represented by the n-tuple consisting of its remainders upon division by
mi
, i = 1, 2, … , n. That is, we can uniquely represent a by
(a mod m1, a mod m2, … , a mod mn).

Question 11

How to perform arithmetic on large numbers?

2 benefits:

Answer 11

To perform arithmetic with large integers, we select moduli m1, m2, … , mn, where each mi
is an integer greater than 2, gcd(mi, mj) = 1 whenever i ≠ j, and m = m1m2 ⋯ mn is greater than
the results of the arithmetic operations we want to carry out.

Once we have selected our moduli, we carry out arithmetic operations with large integers by performing componentwise operations on the n-tuples representing these integers using
their remainders upon division by mi
, i = 1, 2, … , n. Once we have computed the value of each component in the result, we recover its value by solving a system of n congruences modulo
mi, i = 1, 2, … , n. This method of performing arithmetic with large integers has several valuable features.

First, it can be used to perform arithmetic with integers larger than can ordinarily be carried out on a computer. Second, computations with respect to the different moduli can be done in parallel, speeding up the arithmetic.

Question 12

Adding large numbers:

example 8:

Answer 12

To find the sum of 123,684 and 413,456, we work with these 4-tuples instead of these two
integers directly. We add the 4-tuples componentwise and reduce each component with respect
to the appropriate modulus. This yields
(33, 8, 9, 89) + (32, 92, 42, 16)
= (65 mod 99, 100 mod 98, 51 mod 97, 105 mod 95)
= (65, 2, 51, 10).
To find the sum, that is, the integer represented by (65, 2, 51, 10), we need to solve the
system of congruences.

537,140 is the unique nonnegative solution of this
system less than 89,403,930.

Note that it is only when we have to recover the integer represented by (65, 2, 51, 10) that we have to do arithmetic with
integers larger than 100.

Question 13

Good choices for moduli:

Answer 13

Particularly good choices for moduli for arithmetic with large integers are sets of integers of
the form 2^k − 1, where k is a positive integer, because it is easy to do binary arithmetic modulo
such integers, and because it is easy to find sets of such integers that are pairwise relatively
prime. [The second reason is a consequence of the fact that gcd(2^a − 1, 2^b − 1) = 2^gcd(a, b) − 1,
as Exercise 37 in Section 4.3 shows.]

Question 14

FERMAT’S LITTLE THEOREM

Answer 14

If p is prime and a is an integer not divisible by p,
then
a^p−1 ≡ 1 (mod p).
Furthermore, for every integer a we have
a^p ≡ a (mod p).

Fermat’s little theorem tells us that if a ∈ Zp, then a^p−1 = 1 in Zp.

Question 15

modular exponentiation by fermats little thm:

Answer 15

Example 9 illustrated how we can use Fermat’s little theorem to compute a^n mod p, where
p is prime and p̸| a. First, we use the division algorithm to find the quotient q and remainder r
when n is divided by p − 1, so that n = q(p − 1) + r, where 0 ≤ r < p − 1. It follows that
a^n = a^(q(p−1)+r) = ( (a^(p−1))^q )a^r ≡ 1^q.a^r ≡
a^r (mod p). Hence, to find a^n mod p, we only need to compute
a^r mod p. We will take advantage of this simplification many times in our study of number
theory.

Question 16

Pseudoprimes:

and history

Answer 16

We showed that an integer n is prime when it is not divisible by any prime p with
p ≤ √n, but requires us to find all primes not exceeding √n.
ancient Chinese mathematicians believed that n was an odd prime if and only if
2^(n−1) ≡ 1 (mod n).
They
were correct in thinking that the congruence holds whenever n is prime, but they were incorrect
in concluding that n is necessarily prime if the congruence holds.
Unfortunately, there are composite integers n such that 2^(n−1) ≡ 1 (mod n). Such integers are
called pseudoprimes to the base 2.

Question 17

Pseudoprimes definition:

Answer 17

Let b be a positive integer. If n is a composite positive integer, and b^(n−1) ≡ 1 (mod n), then n
is called a pseudoprime to the base b.

Question 18

Testing whether n is prime:

Answer 18

Given a positive integer n, determining whether 2^(n−1) ≡ 1 (mod n) is a useful test that provides some evidence concerning whether n is prime. In particular, if n satisfies this congruence,
then it is either prime or a pseudoprime to the base 2; if n does not satisfy this congruence, it is
composite. We can perform similar tests using bases b other than 2 and obtain more evidence
as to whether n is prime. If n passes all such tests, it is either prime or a pseudoprime to all
the bases b we have chosen.

Furthermore, among the positive integers not exceeding x, where x
is a positive real number, compared to primes there are relatively few pseudoprimes to the
base b, where b is a positive integer. For example, among the positive integers less than 1010
there are 455,052,512 primes, but only 14,884 pseudoprimes to the base 2. Unfortunately, we
cannot distinguish between primes and pseudoprimes just by choosing sufficiently many bases,
because there are composite integers n that pass all tests with bases b such that gcd(b, n) = 1.

Question 19

Definition 2:

Carmichael number:

Answer 19

A composite integer n that satisfies the congruence b^(n−1) ≡ 1 (mod n) for all positive integers b
with gcd(b, n) = 1 is called a Carmichael number.

Question 20

Probabilty of not being a carmichael number, but prime:

Answer 20

Although there are infinitely many Carmichael numbers, more delicate tests, described in
the exercise set, can be devised that can be used as the basis for efficient probabilistic primality
tests. Such tests can be used to quickly show that it is almost certainly the case that a given integer is prime. More precisely, if an integer is not prime, then the probability that it passes a
series of tests is close to 0. We will describe such a test in Chapter 7 and discuss the notions
from probability theory that this test relies on. These probabilistic primality tests can be used,
and are used, to find large primes extremely rapidly on computers.

Question 21

Primitive root:

Answer 21

A primitive root modulo a prime p is an integer r in Zp such that every nonzero element of
Zp is a power of r.

An important fact in number theory is that there is a primitive root modulo p for every
prime p.

Question 22

Discrete Logarithm:

Answer 22

Suppose that p is a prime, r is a primitive root modulo p, and a is an integer between 1 and
p − 1 inclusive. If r^e mod p = a and 0 ≤ e ≤ p − 1, we say that e is the discrete logarithm of
a modulo p to the base r and we write logr a = e (where the prime p is understood).

Question 23

Finding Discrete Logarithms:

Answer 23

The discrete logarithm problem takes as input a prime p, a primitive root r modulo p and a positive integer a ∈ Zp; its output is the discrete logarithm of a modulo p to the base r.
Although this problem might seem not to be that difficult, it turns out that no polynomial
time algorithm is known for solving it. The difficulty of this problem plays an important role in
cryptography, as we will see in Section 4.6.

Question 24

Primitive Root:

Discrete logarithm:

Answer 24

To define discrete logarithms we must first define primitive roots. A primitive root of
a prime p is an integer r such that every integer not divisible by p is congruent to a power of r
modulo p. If r is a primitive root of p and
r^e ≡ a (mod p), then e is the discrete logarithm of a
modulo p to the base r