chapter 2 Modular arithmetic

Question 1

Definition 2.1.1
congruent

Answer 1

Let a, b, m ∈ Z with m > 1. We say that a is congruent to b modulo m, written a ≡ b (mod m),
if a = b + mk for some k ∈ Z. This is equivalent to m | (a − b).

We write a ̸≡ b (mod m) otherwise.

Question 2

Example 2.1.2. 15 mod 3
19 mod 3

Answer 2

15 ≡ 0 (mod 3); 19 ≡ −2 (mod 3)

Question 3

Example 2.1.3 (Clocks).
and modular arithmetic

Answer 3

Again, clocks are the prototypical example of modular arithmetic in every day life. To compute which hour will show on your clock b hours from now, you simply find the unique r ∈ {1, . . . , 12} such that r ≡ a + b (mod 1)2, where a is the hour showing up now.

11 oclock what time in 37hrs?
37≡13≡1 mod 12 12:00

Question 4

Exercise 2.1.4. (1) a ≡ 0 (mod m) if and only if m | a

Answer 4

a ≡ 0 (mod m) means that a =0 +mk=mk for some k ∈ Z, by defn,
and that is exactly the meaning of m | a.

Question 5

Exercise 2.1.4.
(2) a ≡ b (mod m) if and only if a and b have the same remainder on dividing by m.

Answer 5

means a and b have the same remainder upon division by m
Suppose that a ≡ b (mod m). This is equivalent to m|(a-b). Divide a and b by m and write
a=q_1m+r_1
b=q_2m+r_2
m|(A-b) = (q_1-1_2)m +(r_1-r_2)
thus m|(r_1-r_2).

Recall that 0 ≤ r_i < m, so −m < r_1 − r_2 < m.

(There is only one multiple of m between this)
The only number divisible by m in that interval is 0, so
m | (r1 − r2)
if and only if
r1 − r2 = 0, that is, r1 = r2.

Question 6

Exercise 2.1.4
(3) Every integer is congruent modulo m to exactly one of the numbers 0, 1, 2, . . . , m −
1.

Alternatively, to exactly one of 1, 2, . . . , m. We say that {0, 1, . . . , m − 1} and {1, 2, . . . , m} are complete sets of residues modulo m.

Answer 6

(3) Let a ∈ Z and r ∈ Z be its remainder in the division by m. By the previous point, a ≡ r (mod m).

Moreover, if r′ ∈ {0, 1, . . . ,m−1}, its remainder by m is r′ itself, so by the previous point a ≡ r′ (mod m) if and only if r′ = r. This shows that there is a unique r′ ∈ {0, 1, . . . ,m − 1} such that a ≡ r′ (mod m).

If we want to find r′ ∈ {1, . . . ,m}, just take r = r′ when r > 0, and
r′ = m when r = 0.

Question 7

Exercise 2.1.4.
(4) ≡ is an equivalence relation:
(a) a ≡ a for all a (reflexive);
(b) a ≡ b implies b ≡ a (symmetric);
(c) a ≡ b and b ≡ c imply a ≡ c (transitive).

Answer 7

• m | 0, so m | (a − a), meaning that a ≡ a (mod m);
• a ≡ b (mod m) means m | (a − b), but then also m | −(a − b) = (b − a), thus b ≡ a (mod m);
• if a ≡ b (mod m) and b ≡ c (mod m), then m | (a − b) and m | (b − c). This implies also that m | ((a − b) + (b − c)) = (b − c), hence
  b ≡ c mod m.

Question 8

congruence remarks

Answer 8

Every integer is congruent to exactly one of 0,1,…,m-1exactly one of 1,2,…m
n|0

complete sets of residues {1,…,n} and {0,1,…,n-1}

remember working on Z

Question 9

working on Z with mod 2

Answer 9

evens and odds 2 congruence classes
z is partitioned into 2

n=3 we have 3 congruence classes
{3k:k∈ Z}
{3k+1: k∈ Z} ={…,-2,1,4,7,…}
and
{3k+2:k∈ z}

Arithmetic works nicely in these congruence mod m comparable + and -

Question 10

Lemma 2.1.5 (Arithmetic of congruences)

Answer 10

The equivalence relation ≡ (mod m) is compatible with addition and multiplication, meaning that:
if a ≡ b and c ≡ d, then a + c ≡ b + d and ac ≡ bd.

Question 11

PROOF
Arithmetic of congruences)

The equivalence relation ≡ (mod m) is compatible with addition and multiplication, meaning that:
if a ≡ b and c ≡ d, then a + c ≡ b + d and ac ≡ bd

Answer 11

Proof. Take a, b, c, d as in the hypothesis. By assumption, m | (a − b) and m | (c − d). In
particular
m | ((a − b) + (c − d)) = ((a + c) − (b + d))

thus a + c ≡ b + d (mod m). For the product, we need to show that m divides (ac − bd).
We use a trick:
ac − bd = ac − bc + bc − bd = (a − b)c + b(c − d).
Clearly m | (a − b)c + b(c − d), so b | (ac − bd), which means that ac ≡ bc (mod m). □

Question 12

Example 2.1.6. Show that if a ≡ b and c ≡ d, then a − c ≡ b − d, and also a^k ≡ b^k for all
k = 0, 1, 2, . . .

Answer 12

Since −1 ≡ −1, we also have −c ≡ −d, thus a − c ≡ b − d.

For aᵏ we proceed by induction: clearly a_0 = 1 ≡ 1 = b_0;
if aᵏ ≡ bᵏ, then aᵏ⁺¹ = (aᵏ)a ≡
(bᵏ)b = bᵏ⁺¹, and so by induction aᵏ≡ bᵏ for all k.

Question 13

Corollary 2.1.7

CONGRUENCE CLASSES

Answer 13

Let Z/mZ be the set of the congruence classes for the equivalence relation ≡ (mod m); said differently, it is the quotient of Z by the relation ≡ (mod m).
Then Z/mZ is a cyclic group under addition of size m.

In group theory, the ‘cyclic group of order m’ is also called Cm. The main difference between C_m and Z/mZ is that the former is just an abstract group, the latter has multiplication as well.

Question 14

Corollary 2.1.7

CONGRUENCE CLASSES

manual
PROOF

Answer 14

Manual proof. Simply recall that a group is a set with a binary operation which is
associative, has an identity, and every element has an inverse.
* a + (b + c) ≡ (a + b) + c (mod m);
* a + 0 ≡ 0 + a ≡ a (mod m);
* a + (−a) ≡ 0 (mod m).
The set {0, 1, . . . , m − 1} is a complete set of residues and it has size m, so the quotient
has size m. Finally, it is cyclic: its generator is the congruence class of 1.

Question 15

Corollary 2.1.7

CONGRUENCE CLASSES

group theoretic
PROOF

Answer 15

Group theoretic proof. Note that
{a ∈ Z : a ≡ 0 (mod m)} = {mk : k ∈ Z} = mZ.
The set mZ is obviously closed under addition and inverses, so it is a subgroup of Z.
Thus we can take the quotient group Z/mZ. Now recall the definition of quotient
group: two elements a, b ∈ Z are equivalent if and only if a − b ∈ mZ, thus if and only
if m | (a − b), if and only if a ≡ b (mod m). So the quotient group Z/mZ is exactly the
set of congruences we have discussed so far. Since Z is cyclic (it is generated by 1), then Z/mZ is also cyclic and generated by
the quotient of 1. The size is m because again {0, 1, 2, . . . , m − 1} is a complete set of
residues

(2 cosets of a +mZ=b+mZ holds IFF a-b ∈mZ

Question 16

overline(a)

Answer 16

The class of a modulo m is typically denoted by a-, or a + mZ, or [a].

Question 17

Lemma 2.1.8 (Inverses and cancellation)

Answer 17

gcd(a, m) = 1 if and only if there exists b ∈ Z with ab ≡ 1 (mod m).

In particular, if gcd(a, m) = 1 and ax ≡ ay (mod m), then x ≡ y (mod m)

(Any integer coprime to m is invertible mod m)

Question 18

PROOF
gcd(a, m) = 1 if and only if there exists b ∈ Z with ab ≡ 1 (mod m).
In particular, if gcd(a, m) = 1 and ax ≡ ay (mod m), then x ≡ y (mod m)

Answer 18

Proof. Suppose that gcd(a, m) = 1. By Bézout’s Lemma, there are s, t ∈ Z such that
sa + tm = 1. Let b = s: by definition, ab ≡ 1 (mod m). Conversely, suppose that
there is some b such that ab ≡ 1 (mod m). Then ab = 1 + km for some k ∈ Z, that is,
ab − km = 1, thus the greatest common divisor of a and m is 1.

Question 19

necessary condition for inverse b of a mod m

Answer 19

Note that the condition gcd(a, m) = 1 is necessary: for instance, 8 ≡ 12 (mod 4), but
4 ̸≡ 6 (mod 4)!

Question 20

Exercise 2.1.9. Show that if gcd(a, m) > 1, there are x, y ∈ Z such that ax ≡ ay
(mod m) and x ̸≡ y (mod m).

Answer 20

Let d ∈ N be the greatest common divisor of a and m. Then a(m/d)≡
0 ≡ a(2m/d) (mod m).

Now suppose that d > 1.
Then
m/d̸ ≡ 0 (mod m) and so
x := 2(m/d)̸≡ m/d =: y (mod m) satisfy the desired conclusion.

Question 21

Exercise 2.1.10. Show that p is prime if and only if for every a ∈ Z, either a ≡ 0 (mod p) or there is b ∈ Z with ab ≡ 1 (mod p).

Answer 21

For every a ∈ Z we have either gcd(a, p) = 1 or gcd(a, p) = p, because those are the only positive divisors of p. In the former case, there is b such that ab ≡ 1 (mod p); in the latter, a ≡ 0 (mod p).

Question 22

GROUP corollary under x

Answer 22

Corollary 2.1.11. The set
(Z/mZ)×
:= {a ∈ Z/mZ : gcd(a, m) = 1}
is well defined and it is a group under multiplication

checking group axioms: associativity a +b+c ≡a+b+c mod m
operation is taking representatives of equivalence classes and + mod m of congruence

inverse a+ -a ≡0 mod m

Question 23

PROOF
Corollary 2.1.11. The set
(Z/mZ)×
:= {a ∈ Z/mZ : gcd(a, m) = 1}
is well defined and it is a group under multiplication

Answer 23

Proof. First, we need to check that if a- = b-, then gcd(a, m) = 1 implies gcd(b, m) = 1.
Indeed, if gcd(a, m) = 1 there is c such that ac ≡ 1 (mod m), but then bc ≡ ac ≡ 1 (mod m) too, hence gcd(b, m) = 1.
Next, recall that multiplication in Z/mZ is associative, just because it was on Z:
a(bc) ≡ (ab)c (mod m). Likewise, 1 is the multiplicative identity, and of course
1 ∈ (Z/mZ)× , because gcd(1, m) = 1.
Finally, if a, b are coprime with m, then gcd(ab, m) = 1 by Corollary 1.1.12, so (Z/mZ)× is closed under multiplication. Moreover, for each a ∈ (Z/mZ) × , there is b ∈ Z/mZ
such that ab ≡ 1 (mod m); such b must necessarily be in (Z/mZ)×
as well. Therefore,
(Z/mZ)× is a group under multiplication.

Question 24

remark 2.1.12 rings

Answer 24

Remark 2.1.12. The quotient of Z/mZ is actually a ring, that is to say, a set with a sum and product satisfying certain properties (associativity, distributivity, etc). (In fact, if you know rings, you can verify that mZ is an ideal of Z, and so quotienting by mZ
gives us a ring.)

We do not use this language now, for simplicity, but keep this idea in the background: we will talk again about rings towards the end of the module

Question 25

Example 2.2.1 (Digits). Since 10 ≡ 1 (mod 9), we have 10^n ≡ 1^n = 1 (mod 9) for any n.

checking a numbers sum of digits

Answer 25

Therefore, every number is congruent to the sum of its digits modulo 9:

10^n d_n + 10^{n-1}d_n +…+ d_0 ≡ d_n + · · · + d_0 (mod 9).

For instance, 3456 =
10^3· 3 + 10^2· 4 + 10 · 5 + 6
≡ 1^3· 3 + 1^2· 4 + 1 · 5 + 6 = 18 ≡
1 + 8 = 9 ≡ 0 (mod 9).

as 10 ≡1 mod 9
10^n ≡1^n =1 mod 9
any integer is congruent mod 9 to the sum of its digits
9|171 as 9 | 1+7+1

Question 26

Example 2.2.2 (Yet more digits). Let us compute the decimal expansion

Answer 26

0.q₁q₂q₃…. of 1/7

each q_k computed as follows
* we start with r_0 = 1, the numerator of 1/7 ; note that 0 ≤ r_0 < 7 (otherwise we would have to do some extra steps!);

• inductively, divide 10r_k by 7 and find quotient q_{k+1}, remainder r_{k+1}
  . You can check this manually: 10 = 1 · 7 + 3, thus q1 = 1, r1 = 3; 30 = 4 · 7 + 2, so q2 = 4,
  r2 = 2, and so on.
  By construction, r_{k+1} ≡ 10r_k (mod 7), thus r_k ≡ 10^k (mod 7). But now we notice that
  10^6 ≡ 1 (mod 7): indeed, 10^6 ≡ 3
  6 ≡ 2^3 = 8 ≡ 1 (mod 7). Therefore, r_6 = 1, and
  more generally r_{k+6} = r_k. In particular, q_{k+6} = q_k , so the expansion is periodic with
  period of length (a divisor of) 6. The length is exactly 6 because you can also check that none of 10, 10^2, . . . , 10^5 are congruent to 1 modulo 7.

if you evaluate it it comes in blocks of 6, period of 6. so 10^6=1+7k some k and 6 is least period with the property

period of 1/7 is the smallest r s.t 10^r=1+7k for some k
checking powers of 10 congruent to mod 7 we find this

Question 27

Exercise 2.2.3. Compute the length of the period of 1/3,1/9,1/11 just by looking at the least k > 0 such that 10k ≡ 1 modulo respectively 3, 9, and 11. What happens for 1/2?

Answer 27

leads to fermats little thm….

Question 28

Fermat’s little theorem
thm 2.2.4

Answer 28

Let p be a prime and a ∈ Z such that p ∤ a.
Then aᵖ−¹ ≡ 1 (mod p)

whenever p is prime and we take an integer coprime to p

then it’s p-1 th power is congruent to 1 mod p

any integer as long as its not divisible by p

Question 29

PROOF of Fermat’s little theorem

Let p be a prime and a ∈ Z such that p ∤ a. Then a
p−1 ≡ 1 (mod p)

Answer 29

write down

Group theoretic proof. By Corollary 2.1.11, the congruence classes of 1,…, p − 1 form a group under multiplication. Its size is p − 1 by Exercise 2.1.10: by Lagrange’s theorem, ap−1 ≡ 1 (mod p)forevery element of the group. □ Combinatorial proof. The numbers a,2a,3a,…,(p −1)a are not divisible by p, so they are not congruent to 0 modulo p. Moreover, if ra ≡ sa (mod p), then r ≡ s (mod p) by Lemma2.1.8, since gcd(a, p) = 1. It follows that the numbers a,2a,3a,…,(p −1)a are just some permutation of 1,2,…,(p −1) modulo p. In particular ap−1(p −1)! = p−1 ∏ k=1 ak ≡ p−1 ∏ k=1 k =(p−1)! (mod p). But (p−1)! is also not divisible by p, so by Lemma 2.1.8 again, we can cancel it out and f ind that ap−1 ≡ 1 (mod p). □ Extra. As it turns out, Fermat did not prove this theorem either. Exercise 2.2.5. Show that the decimal expansion of 1 p for p prime different from 2, 5 has period of length at most p −1 (and must divide p−1).

Question 30

Alt form of Fermat’s little theorem

(Corollary 2.2.6 (Alternative form of Fermat’s Little Theorem).)

Answer 30

p prime, a ∈ Z
implies
Then aᵖ ≡ a (mod p)

(any integer, could be divisible by p!)
(comes from the fact that if p doesnt divide a then we can divide both sides by a; if it is then its congruent to 0 mod p

Question 31

PROOF for
Corollary 2.2.6 (Alternative form of Fermat’s Little Theorem).

Answer 31

If p | a, then a ≡ 0 and a
p ≡ 0; otherwise p ∤ a, thus aᵖ⁻¹ ≡ 1, hence aᵖ ≡ a just
by multiplying both sides by a.

Question 32

Applications of Fermat’s little thm

Exercise 2.2.5. Show that the decimal expansion of 1/p for p prime different from 2, 5 has period of length at most p − 1 (and must divide p − 1)

Answer 32

We have seen that the length of the period is the least positive integer k such that
10ᵏ ≡ 1 (mod p)
(provided p ∤ 10).

By Fermat’s Little Theorem, we also have 10ᵖ−¹ ≡ 1 (mod p) (again we use that p ∤ 10).

As k is the least integer p-1 must be divisible by k.

Now divide p − 1 by k, that is write p − 1 =qk + r where 0 ≤ r < k. Then
1 ≡ 10ᵖ−¹ = (10ᵏ)ᵠ10ʳ ≡ 10ʳ (mod p). By minimality
of k, we must have r = 0, that is k | p − 1.

Question 33

Proposition 2.2.8.

every prime factor of 2ʳ-1 has

Answer 33

Let r > 2 be a prime. Then every prime factor of 2ʳ − 1 is of the form
2kr + 1.

Question 34

prop 2.2.8 proof
Let r > 2 be a prime. Then every prime factor of 2ʳ − 1 is of the form
2kr + 1.

Answer 34

Let r>2 prime, take p prime divisor of 2ʳ − 1.

Suppose that p | 2ʳ − 1 for some prime p. This means 2ʳ ≡1 (mod p),

By Fermat’s little theorem we have that 2ᵖ⁻¹≡1 (mod p).

2ʳ − 1 is odd so p>2, so gcd(p,2)=1 ( so p ∤2).
(we have two ≡ here now similar to prev proof)
We claim r | p − 1, we assume otherwise and look for a contradiction.

Suppose that r ∤ p − 1.
Since r is prime, gcd(r, p-1)=1 thus by lemma 2.1.8 there is a b ∈ Z such that (p − 1)b ≡ 1 (mod r).

b can be replaced with any number congruent to b, so we can assume b>0.

We have found b s.t (p − 1)b = 1 + rk for some k ∈ Z, and actually k > 0 since
b > 0. Then

(2⁽ᵖ⁻¹⁾)ᵇ ≡ (1)ᵇ= 1 (by FLittleT)
= 2¹⁺ʳᵏ = 2 . (2ʳ)ᵏ (by (p − 1)b = 1 + rk)
≡2 (1ᵏ).2 (by 2ʳ ≡1 mod p)

thus 1≡2 mod p implies 1≡0 mod p
p does not divide 2, p is prime gives our contradiction

mod p
“typo in notes mod r should be mod p”

notes:
1 = 1ᵇ ≡ 2⁽ᵖ⁻¹⁾ᵇ = 2¹⁺ʳᵏ
= 2 · (2ᵏ)ʳ ≡ 2 (mod r),
a contradiction since {0, . . . ,r − 1} is a complete set of residues modulo r.

We must then have r | p − 1. Since p is odd, p − 1 is even, and by assumption r is odd, so gcd(2,r) = 1, thus 2r | p − 1. By defn of divisibility , p = 2kr + 1 for some k ∈ Z.

Question 35

Exercise 2.2.7 (in exercise sheet).

Let r ∈ N. Prove that if 2ʳ − 1 is prime, then r is prime

Answer 35

not gone through? .

Question 36

Mersenne prime

Answer 36

2ʳ − 1 if 2ʳ − 1 is prime

we also know this implies r is prime

e.g
2²-1=3
2³-1=7
2⁵-1= 31
2⁷-1=127

however
2¹¹-1 is divisible by 23

The largest known prime number (as of January 2024) is
2²⁸²,⁵⁸⁹,⁹³³ − 1, a Mersenne prime (the 51st, to be precise).

Question 37

ex Find the smallest prime divisor of 2²³ -1

Example 2.2.9. We have seen that 23 | 2¹¹ − 1, and indeed 23 = 2 · 1 · 11 + 1. What about
2²³ -1? Is it prime?

Answer 37

By proposition every prime factor of 2²³ -1 is of the form 46k+1
The first prime in this form r=47. Thus we work in mod 47:
2⁵=32≡-15
2¹⁰=(2⁵)²≡(-15)² = 225 ≡ 37=-10
2²⁰=(2¹⁰)²≡ (-10)²=100≡6
2²³=6.8=48≡1

Showing 47 divides 2²³ -1 and so 2²³ -1 isn’t prime

Question 38

Theorem 2.3.1 (Wilson’s Theorem (al-Haytham c. 1000))

Answer 38

If p is prime, then (p − 1)! ≡ −1 (mod p).

Question 39

Example 2.3.2.
using Wilson’s thm p=11

Answer 39

p=11 and is prime then
10! ≡−1 (mod 11).
as seen
2 · 6 ≡ 3 · 4 ≡ 5 · 9 ≡ 7 · 8 ≡ 1 (mod 11)
(bc p is prime these numbers will have an inverse)
thus
10! =1.2.3.4.5.6.7.8.9.10≡ 10 ≡ −1

Question 40

Corollary 2.3.3. of Wilson’s thm

Answer 40

If p is prime, then the congruence equation x²≡ −1 (mod p) has a
solution if and only if p = 2 or p = 4k + 1 for some k ∈ Z (that is, p ≡ 1 (mod 4)).

Question 41

Wilsons thm proof
If p is prime, then (p − 1)! ≡ −1 (mod p).

Answer 41

For every a ∈ {1, . . . , p − 1}, there is a unique
b ∈ {1, . . . , p − 1} such that ab ≡ 1 (mod p).
(inverse exists in integers, unique as p is prime )

Whenever a ̸≡ b, both a and b appear in
(p − 1)!, and we can cross them off

(p-1)!= ∏ₐ₌₁ᵖ⁻¹ a ≡ ∏ₐ₌₁, ₐ₂≡₁ ᵖ⁻¹ of a
(remove values with inverse, keep those s.t a is own inverse)
which a’s satisfy a²≡1?
occurs iff p | (a² − 1) = (a + 1)(a − 1). Since p is prime, we have either p | (a + 1) or p | (a − 1), that is a ≡ ±1

thus
= 1 · (p − 1) = p − 1

Question 42

proof of corollary of Wilson’s
If p is prime, then the congruence equation x² ≡ −1 (mod p) has a solution

if and only if

p = 2 or p = 4k + 1 for some k ∈ Z (that is, p ≡ 1 (mod 4)).

Answer 42

if p=1 then x=1 is a sol

case: p>2 and focus on p odd and p-1 even

Suppose there is a solution a s.t a² ≡ −1 (mod p) . By FLittleT,
1≡aᵖ⁻¹ (mod p), because p cannot divide a by the assumption of it being a solution to the above.

re-write as p is odd:
1≡aᵖ⁻¹= (a²)⁽ᵖ⁻¹⁾/² ≡(-1)⁽ᵖ⁻¹⁾/² (mod p)

since 1 is not congruent to -1 mod p: (p-1)/2 must be divisible by 2 as must be even, thus 4 |(p − 1).

conversely:
Suppose p ≡ 1 (mod 4)
(p − 1)! = 1 · 2….(p-1)/2 . (p+1)/2….(p-2).(p-1)
(p is odd, we split in half, we know ≡ by subtracting p from factors in the last half)

≡1 · 2….(p-1)/2 .[-(p-1)/2]….(−1) · (−1)
=( (p-1)/2))!· (-1)⁽ᵖ⁻¹⁾/² ( (p-1)/2))!·
= (( (p-1)/2))!)² · (-1)⁽ᵖ⁻¹⁾/²

Now by Wilsons, LHS ((p − 1)!) congruent to -1 and (p-1)/2 is even by assumption thus (-1)⁽ᵖ⁻¹⁾/² ≡ 1.

Follows that x = ((p-1))/2)! satisfies the eq

Question 43

Theorem 2.4.1 (Chinese Remainder Theorem (Qin Jiushao 秦九韶, 1247))

Answer 43

If m₁, . . . , mₖ are pairwise coprime integers and a₁, . . . , aₖ ∈ Z, then the simultaneous congruences

x ≡a₁ (mod m₁)
x ≡a₂ (mod m₂)
…
x ≡aₖ (mod mₖ )
have a solution x ∈ Z. Moreover, any two solutions are congruent modulo m₁, . . . , mₖ

we say sol is unique up to congruence modulo m₁, . . . , mₖ’
.

Question 44

background my exercises:
Find x such that 3x ≡ 7 (mod 10)

Answer 44

multiplicative inverse for 3 mod 10 are
3ᵠ⁽¹⁰⁾−¹. and q(10)=4 so the inverse of 3 mod 10 is
3³≡ 27 ≡ 7 (mod 10)

take eq and multiply both sides by 7
x ≡ 49 ≡ 9 (mod 10)
x=9

Question 45

background ex:
Find x such that 3x ≡ 6 (mod 12).

Answer 45

no multiplicative inverse
if there is a sol this means 3x-6 is divisible by 12, so there is some k ∈ Z s.t 3x-6=12k. Working in integers we can divide by 3. x-2=4k hence x ≡ 2 (mod 4)

Question 46

background ex:
Example 5. Use the Chinese Remainder Theorem to find an x such that
x ≡ 2 (mod 5)
x ≡ 3 (mod 7)
x ≡ 10 (mod 11)

Answer 46

N=5x7x11=385
m_1=N/5=77
m_2=N/7=55
m_3=N/11=35

seek multiplicative inverse for each m_i mod n_i
m_1 ≡ 77 ≡ 2 (mod 5) has inverse y_1=3
m2 ≡ 55 ≡ 6 (mod 7), inverse to m_2 mod n_2 is y_2 = 6
m3 ≡ 35 ≡ 2 (mod 11), an inverse to m3 mod n3 is y3 = 6.
Therefore, the theorem states that a solution takes the form:

x = y_1b_1m_1 + y_2b_2m_2 + y_3b_3m_3
= 3 × 2 × 77 + 6 × 3 × 55 + 6 × 10 × 35 = 3552.

Since we may take the solution modulo N = 385, we can reduce this to 87, since 2852 ≡87 (mod 385).

Question 47

Example in lecture: find the solution for x s,t
x ≡2 mod 3
x ≡3 mod 5

Answer 47

x=8, x=23 is a sol by deduction but…

by thm:

x=3y_1+ 5y_2

found by solving
5y_2 ≡ 2 mod 3
cancels out as 5 ≡ 2
3y_1 ≡ 3 mod 5
y_1=1
y_2=1

x=8 is a solution

Question 48

Example in lecture: find the solution for x s,t
x ≡2 mod 3
x ≡4 mod 9

Answer 48

3 and 9 not coprime

(4+3(3k)= 2+3(m) ???)
has no solution as this means
x ≡2 mod 3
x ≡4 mod 9 means x ≡1 mod 3 which doesn’t work

Question 49

Proof for chinese remainder theorem

If m₁, . . . , mₖ are pairwise coprime integers and a₁, . . . , aₖ ∈ Z, then the simultaneous congruences

x ≡a₁ (mod m₁)
x ≡a₂ (mod m₂)
…
x ≡aₖ (mod mₖ )
have a solution x ∈ Z. Moreover, any two solutions are congruent modulo m₁, . . . , mₖ

we say sol is unique up to congruence modulo m₁, . . . , mₖ
.

Answer 49

Base case k=2:
take x of the form x=m₁y₁+m₂y₂
so we have
x ≡ m₁y₁=a₂ mod m₂ (1)
x ≡ m₂y₂ =a₁ mod m₁ (2)

2 equations in 2 vars (e.g solving m₁y₁=a₂ and we know m₁ coprime to m₂)

(notes: By lemma 2.1.8 there are c and b s.t.)

Take c s.t m₂c≡1 (mod m₁)
Take b s.t m₁b≡1 (mod m₂)

thus
y₂ ≡ca₁ mod m₁
y₁ ≡ba₂ mod m₂ (from y₁=(1)y₁ ≡(m₁b)y₁= (m₁y₁)b ≡ba₂)

use x = m₁ba₂+ m₂ca₁
as a solution

For k>2 reason by induction:

Find y s.t
y solves system up to k-1
y ≡a₁ (mod m₁)
y ≡a₂ (mod m₂)
…
y ≡aₖ₋₁ (mod mₖ₋₁ )

Then solve system
x≡y mod m₁, . . . , mₖ₋₁
x≡aₖ mod mₖ

notes give slightly different proof?

Finally we show the solution is unique, suppose that x, y are two solutions. In particular, x − y ≡ 0 (mod mᵢ) for every i=1,…,k
thus we have mᵢ |(x − y). Since the mᵢ’s are pairwise coprime, it follows that m₁· … · mₖ| (x − y), that is, x ≡ y (mod m₁· … · mₖ )

Question 50

Group theory interpretation approach: chinese remainder thm proof

Answer 50

The thm is saying that if we take the group
(Z/(m₁· … · mₖZ), +) under addition
(integers mod m_1 to m_k)

we have (m₁· … · mₖ) elements as elements are represented by 0,1,2,…m_1?m_k-1???

“this is isomorphic to the
group product” of each group with m_1 elements x…. x m_k elements
the group
{Z/m_1Z x …. x Z/ m_kZ} set as the cartesian product
number of tuples is m_1· … · mₖ

This is a bijection between the cartesian product partition of congruence classes modulo m_1 to m_k
and congruence classes between m_1 to m_k

Question 51

Why is it true: We have seen that the length of the period is the least positive integer k such that
10^k = 1 (mod p)
(provided p doesn’t divide 10).

Answer 51

This statement is a consequence of Fermat’s Little Theorem. It states that if
p is a prime number not dividing 10, then
10^{p−1}
≡1
(mod p). Therefore, the length of the period (or the order of 10 modulo
p) must divide p−1.

Question 52

Wilson’s thm example corollary

Answer 52

Example 2.3.4. Start with p = 13 ≡ 1 (mod 4). Take x = (p−1)/2 ! = 6! = 720 ≡ 5 2
(mod 13)

Indeed we have 5^2 = 25 ≡ −1 (mod 13)