%%visits: 2 ## introduction ## intuition modulo is an [[equivalence_relation]]
The difference between a residue class and a congruence class is that residue class elements are numbers, but congruent classes are not numbers.
Arithmetic of modulo
[a]m + [b]m = [a + b]m
[a]m[b]m = [ab]m
ℤm is a ring ##
rigour modul := Let m be a non-zero integer, and let
a, b ∈ ℤ. We say that
a is congruent to
b modulo m, if m|(a − b) We write
this as a ≡ b(modm)
where m is the modulus. congruence clas := $_{m} = { b : b
a (mod ) } $ residue syste := Let m be a positive integer. A set {x1, x2, …xr}
is called a complete residue system modulo m, if for ever
integer y there is exactly one xi such that
y ≡ xi(modm)
set of congruence classe := ring of integer :=
For a positive integer m, we let ℤm denote the set of
congruence classes modulo m,
also called ring of integer modulo m. ℤ3 = {[0]3, [1]3, [2]3}
## exam clinic [2]3 = {3k + 2, k ∈ ℤ} = {2, 5, −1, 7…}
==resources residue class for m=4 is ${ 0,1,2,3 } $ or ${ 1,2,3,4 } $ in
fact any set of the form {n, n + 1, n + 2, n + 3}
where n ∈ ℤ
Luckily, to find an inverse of 48 is easy, since gcd of the two are 1. 85(13) − 48(23) = 1
⟹ (−23)48 ≡ 1 ⟹ (−23)48x ≡ −23(71) mod 85 ⟹ −23(71) mod 85
for f(x) = a0 + a1x + ..anxn with aj ∈ ℤ, solve f(x) ≡ 0 mod m
Remark [f]m(x) = [a0]m + [a1]mx + … + [an]mxn
Use $5 = { {5} , {5}, {5} , {5}, {5}} $ to take advantage of the squaring. of X
We know x2 ≡ 4 mod 15 ⇔ x2 ≡ 4 mod 3 and x2 ≡ 4 mod 5. Which decomposes the problem quickly, however, we need the [[chinese_remainder_theorem]].
This is −1 mod 3 or −2 mod 5. Which creates 4 different permutations
arithmetic modulo n
Let a, b, m, n ∈ ℤ, m, n ≥ 1. Prove that the system of congruences x ≡ a mod mx ≡ b mod n has solutions ⇔ gcd (m, n)|a − b If a solution exists, h
tags :math:introduction_to_number_theory:introduction_to_abstract_algebra: