Skip to content

INFO

Tính chia hết và số học đồng dư

Division ​

  • For 2 integers a and b, a ≠ 0, a divides b (a|b) if it exists an integer k such that b=a.k
  • Express using quantifier
a|b: ∃k(a.k=b) where x is set of integer
  • a is a factor or divisor of b (a là uớc, số chia của b)
  • b is a multiple of a (b là bội của a)

Theorem 1 ​

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

👆

if a∣b and a∣c , then a∣(b+c)

👆

if a∣b then a∣bc for all integer c

🥉

if a∣b and b∣c , then a∣c

Corollary 1 ​

👉

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.

Theorem 2 (Division algorithm) ​

👉

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.

  • In the equality:
    • d is called the divisor (số chia)
    • a is called dividend (số bị chia)
    • q is called quotient (thương)
    • r is called remainder (số dư)
  • We have notation for q and r:
q=a div d=⌊a/d⌋, and r=a mod d=a−d

Modular Arithmetic (số học đồng dư) ​

Congruent (đồng dư thức) ​

  • 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 m|(a−b)
a≡b(mod m)
  • m is called modulus (plural moduli) - mẫu số đồng dư

Theorem 3 ​

👉

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.

  • Proof,

Theorem 4 ​

👉

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.

  • Proof, use direct proof from the definition of congruence

Theorem 5 ​

  • Let m be a positive integer. If a≡b(mod m) and c≡d(mod m), then
    • a+c≡b+d(mod m)
    • a.c≡b.d(mod m)
  • Proof, direct proof

Corollary 2 ​

image.png

Arithmetic Modulo m ​

Definition ​

  • We can define arithmetic operations on Zm, the set of non-negative integers less than m, that is, the set {0,1,...,m−1}.
  • In particular, we define the addition of these integers, denoted by +m (use + for simplicity) by
a+b=(a+b) mod ma.b=(a.b) mod m
  • They also satisfy many of the same properties of ordinary addition and multiplication of integers.
  • In particular, they satisfy these properties:

Properties ​

  • Closure (Tính đóng)
If a,b∈Zm, then a+b∈Zm and a⋅b∈Zm
  • Associativity (Tính kết hợp)
If a,b,c∈Zm, then (a+b)+c=a+(b+c) and (a⋅b)⋅c=a⋅(b⋅c)
  • Commutativity (Tính giao hoán)
If a,b,c∈Zm, then a+b=b+a , and a⋅b=b⋅a
  • Identity elements (Phần tử đơn vị)

👉

The elements 0 and 1 are identity elements for addition and multiplication modulo m, respectively

  • Additive inverses (Phần tử đối), not be applied for multiplicative
If a≠0 and a∈Zm, then m−a is additive inverse of a modulo m, 0 is its own additive inverse.a+(m−a)=0 and 0+0=0.
  • Distributivity (phân phối)
If a,b,c∈Zm, then a⋅(b+c)=(a⋅b)+(a⋅c), and (a+b)⋅c=(a⋅c)+(b⋅c)

Built with ❤️ and curiosity