chinese_remainder_theorem

introduction

%%visits: 5 ## intuition The ring theoretic statement of chinese_remainder_theore := Let m, n be co-prime ψ : ℤmn → ℤm × ℤn Given by ψ([a]mn) = ([a]m, [a]n) is a bijection (also a ring isomorphism)

Inverse elements

Let m be a positive integer and let a ∈ ℤ. If gcd (a, m) = 1 then there exists b ∈ ℤ such that ab ≡ 1 mod m

Proof. Bezouts_lemma  ⟹ ∃u, v ∈ ℤ

au + vm = 1 ⟹ au = −vm + 1 ⟹ au ≡ 1 mod m

multiplicative_group_of_integers and inverses

What is a unit. Given a commutative ring R with identity 1R we call a ∈ R a unit if there exists b ∈ ℝ such that a ⋅ b = 1R

ℤmn. Related to ℤmℤn ## rigour Let m, n be coprime integers. Then the system of modular equations. x ≡ a mod m and x ≡ b mod n has a unique solution mod mn let m,n >1 : gcd(m,n) = 1 let a,b be arbitrary integers there is an integer x which satisfies x ≡ a (mod m) x ≡ b (mod n) and the solution of these simultaneous equations are given by all x ≡ x0 (mod mn)

Proof of chinese_remainder_theorem Existence By [[Bezouts_lemma]], there exists u, v ∈ ℤ such that um + vn = 1. So [vn]m = [1]m. And [um]n = [1]n

Consider, X = bum + avn [X]m = [bum + avn]m = [avn]m = [a]m

[X]n = [bum + avn]n = [bum]n = [b]n

uniqueness

X ≡ a mod m X ≡ a mod m

X ≡ b mod n Y ≡ b mod n

So X ≡ Y mod m  ⟹ m|x − y

So X ≡ Y mod n  ⟹ n|x − y ## exam clinic Let f(x) = x21 + a20x20 + … + a1x + a0 with a21, …, a1, a0 ∈ ℤ. What is the nlargest number of solutions to f(x) ≡ 0 mod 186 in ℤ186 186 = 2 ⋅ 3 ⋅ 31

ℤp is a field (not the case when composite)

exam_clinc

1.Let f(x) = X21 + a20X20 + … + a1X + a0 what is the largest number of solutios to f(x) ≡ 0 mod 186

using chinese_remainder_theorem ℤ186 ↔︎ ℤ2 × ℤ3 × ℤ31 (this is injective)

  1. f(x) ≡ 0 mod 2 which is less than or equal to the order of the group.
  2. f(x) ≡ 0 mod 3 which is less than or equal to the order of the group.
  3. f(x) ≡ 0 mod 31 which is less than or equal to the order of the group, but the number of solutions possible is bounded by 21

So we times all possible permutations (chose with replacement)

so answer 2 ⋅ 3 ⋅ 21 = 126 ## resources tags :math:introduction_to_abstract_algebra:introduction_to_number_theory:

backlinks