4.1 Divisibility and Modular Arithmetic

Question 1

Number Theory:

Answer 1

The part of mathematics devoted to the study of the set of integers and their properties is
known as number theory.

Question 2

Modular Arithmetic:

Answer 2

Modular arithmetic operates with the remainders of integers when they are divided by a fixed positive integer, called the modulus.

Question 3

Division Definition: and terms multiple, divisor, factor.
and notation.

Denote using quantifiers:

Answer 3

If a and b are integers with a ≠ 0, we say that a divides b if there is an integer c such that
b = ac (or equivalently, if b/a is an integer). When a divides b we say that a is a factor or
divisor of b, and that b is a multiple of a. The notation a ∣ b denotes that a divides b. We
write a̸| b when a does not divide b.

We can express a ∣ b using quantifiers as
∃c(ac = b),
where the universe of discourse
is the set of integers.

Question 4

3 basic properties of divisibility of integers:

Theorem 1

Answer 4

Let a, b, and c be integers, where a ≠ 0. Then

(i) if a ∣ b and a ∣ c, then a ∣ (b + c);
(ii) if a ∣ b, then a ∣ bc for all integers c;
(iii) if a ∣ b and b ∣ c, then a ∣ c.

Question 5

Corollary 1

If a, b, and c are integers, where a ≠ 0, such that a ∣ b and a ∣ c:

Answer 5

If a, b, and c are integers, where a ≠ 0, such that a ∣ b and a ∣ c, then a ∣ mb + nc whenever
m and n are integers.

Question 6

THE DIVISION ALGORITHM

Answer 6

Let a be an integer and d a positive integer. Then there are unique integers q and r, with 0 ≤ r < d, such that a = dq + r
Note: r is not negative.

Question 7

Terminology of the dividion algo..etc
and equations with just q on LHS, just r on LHS, using just one operator.

This notation is used to express the
quotient and remainder:

Remark:

Answer 7

In the equality given in the division algorithm, d is called the divisor, a is called the dividend,
q is called the quotient, and r is called the remainder. This notation is used to express the
quotient and remainder:
q = a div d, r = a mod d.

Note that both a div d and a mod d for a fixed d are functions on the set of integers. Furthermore, when a is an integer and d is a positive integer, we have
a div d = ⌊a∕d⌋
and a mod d = a − d.

Question 8

Mod in programming languages:

Answer 8

A programming language may have one, or possibly two, operators for modular arithmetic, denoted by mod (in BASIC, Maple, Mathematica, EXCEL, and SQL), % (in C, C++,Java, and Python),
rem (in Ada and Lisp), or something else. Be careful when using them, because
for a < 0, some of these operators return a − m⌈a∕m⌉ instead of a mod m = a − m⌊a∕m⌋
(as shown in Exercise 24). Also, unlike a mod m, some of these operators are defined when
m < 0, and even when m = 0.

Question 9

Congruence:

difference btw this mod and prev mod.

Answer 9

( notation
that indicates that two integers have the same remainder when they are divided by the positive
integer m. )
If a and b are integers and m is a positive integer, then a is congruent to b modulo m if m divides a − b. We use the notation a ≡ b (mod m) to indicate that a is congruent to b modulo m.
We say that a ≡ b (mod m) is a congruence and that m is its modulus (plural moduli). If a
and b are not congruent modulo m, we write a ≢ b (mod m).

Although both notations a ≡ b (mod m) and a mod m = b include “mod,” they represent fundamentally different concepts. The first represents a relation on the set of integers, whereas the
second represents a function.

Question 10

a ≡ b (mod m) in terms of mod function, thm 3:

Answer 10

Let a and b be integers, and let m be a positive integer. Then a ≡ b (mod m) if and only
if a mod m = b mod m.

( a ≡ b (mod m) if and only if a and b have the same remainder when divided by m )

Question 11

When are the integers a and b are congruent modulo m?

Theorem 4.

Answer 11

Let m be a positive integer. The integers a and b are congruent modulo m if and only if there
is an integer k such that a = b + km.

Question 12

Congruence Class:

and relate those classes to set of ints.

Answer 12

The set of all integers congruent to an integer a modulo m is called the congruence class
of a modulo m.
 In Chapter 9 we will show that there are m pairwise disjoint equivalence classes
modulo m and that the union of these equivalence classes is the set of integers.

Question 13

Theorem 5:

Addition and mutlipciation of congruences:

and other invalid properties:

Answer 13

Let m be a positive integer. If a ≡ b (mod m) and c ≡ d (mod m), then
a + c ≡ b + d (mod m) and ac ≡ bd (mod m).

Some properties we may expect to be true
are not valid. For example, if ac ≡ bc (mod m), the congruence a ≡ b (mod m) may be false.
Similarly, if a ≡ b (mod m) and c ≡ d (mod m), the congruence a^c ≡ b^d (mod m) may be false

Question 14

Corollary 2 shows how to find the values of the mod m function at the sum and product of
two integers using the values of this function at each of these integers.:

Answer 14

Let m be a positive integer and let a and b be integers. Then
(a + b) mod m = ((a mod m) + (b mod m)) mod m
and
ab mod m = ((a mod m)(b mod m)) mod m.

Proof: By the definitions of mod m and of congruence modulo m, we know that a ≡
(a mod m) (mod m) and b ≡ (b mod m) (mod m)

Question 15

Arithmetic Modulo m

the set Zm:
addition and multiplication modulo m:

Answer 15

We can define arithmetic operations on Zm, the set of nonnegative integers less than m, that is,
the set {0, 1, … , m − 1}.
In particular, we define addition of these integers, denoted by +m by

a +m b = (a + b) mod m,

and we define multiplication of these integers, denoted by ⋅m by

a ⋅m b = (a ⋅ b) mod m,

The operations +m and ⋅m are called addition and multiplication modulo m and when
we use these operations, we are said to be doing arithmetic modulo m

Question 16

Properties satisfied by addition and multiplication modulo m:
6

Answer 16

1. Closure: If a and b belong to Zm, then a +m b and a ⋅m b belong to Zm.
2. Associativity: If a, b, and c belong to Zm, then (a +m b) +m c = a +m (b +m c) and
   (a ⋅m b) ⋅m c = a ⋅m (b ⋅m c).
3. Commutativity If a and b belong to Zm, then a +m b = b +m a and a ⋅m b = b ⋅m a
4. Identity elements The elements 0 and 1 are identity elements for addition and multiplication
   modulo m, respectively. That is, if a belongs to Zm, then a +m 0 = 0 +m a = a and
   a ⋅m 1 =1 ⋅m a = a.
5. Additive inverses If a ≠ 0 belongs to Zm, then m − a is an additive inverse of a modulo m and
   0 is its own additive inverse. That is, a +m (m − a) = 0 and 0 +m 0 = 0.
6. Distributivity If a, b, and c belong to Zm, then a ⋅m (b +m c) = (a ⋅m b) +m (a ⋅m c) and
   (a +m b) ⋅m c = (a ⋅m c) +m (b ⋅m c). ?? not.

Multiplicative Inverse don’t always exist.

Question 17

Commutative group, commutative ring:

Answer 17

Because Zm with the operations of addition and multiplication modulo m satisfies the
properties listed, Zm with modular addition is said to be a commutative group and Zm with both
of these operations is said to be a commutative ring.