Shawn Zhong

Shawn Zhong

 钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Shawn Zhong

 钟万祥
  • Tutorials
  • Mathematics
    • Math 240
    • Math 375
    • Math 431
    • Math 514
    • Math 521
    • Math 541
    • Math 632
    • Abstract Algebra
    • Linear Algebra
    • Category Theory
  • Computer Sciences
    • CS/ECE 252
    • CS/ECE 352
    • Learn Haskell
  • AP Notes
    • AP Microecon
    • AP Macroecon
    • AP Statistics
    • AP Chemistry
    • AP Physics E&M
    • AP Physics Mech
    • CLEP Psycho

Home / 2018 / March / 12

4.4 Solving Congruences

  • Mar 12, 2018
  • Shawn
  • Math 240
  • No comments yet
Linear Congruences • Definition ○ A congruence of the form ax≡b (mod m), ○ where m is a positive integer, a and b are integers, and x is a variable ○ is called a linear congruence. ○ The solutions to a linear congruence ax≡b (mod m) are ○ all integers x that satisfy the congruence. • Definition ○ An integer ā such that āa≡1 (mod m) is said to be an inverse of a modulo m. • Example ○ 5 is an inverse of 3 modulo 7 since 5∙3=15≡1 (mod 7) • One method of solving linear congruences makes use of an inverse ā, if it exists. • Although we can not divide both sides of the congruence by a • we can multiply by ā to solve for x. Inverse of a modulo m • The following theorem guarantees that • an inverse of a modulo m exists whenever a and m are relatively prime. • Two integers a and b are relatively prime when gcd(a,b) = 1. • Theorem 1 ○ If a and m are relatively prime integers and m 1, then an inverse of a modulo m exists. ○ Furthermore, this inverse is unique modulo m. ○ So, there is a unique positive integer ā less than m that is an inverse of a modulo m ○ And every other inverse of a modulo m is congruent to ā modulo m • Proof ○ Since gcd(a,m) = 1 ○ By Theorem 6 of Section 4.3, there are integers s and t such that sa + tm = 1. ○ Hence, sa + tm ≡ 1 (mod m). ○ Since tm ≡ 0 (mod m), it follows that sa ≡ 1 (mod m) ○ Consequently, s is an inverse of a modulo m. ○ The uniqueness of the inverse is Exercise 7. Finding Inverses • The Euclidean algorithm and Bézout coefficients gives us • a systematic approaches to finding inverses. • Find an inverse of 3 modulo 7. ○ Because gcd(3,7) = 1, by Theorem 1, an inverse of 3 modulo 7 exists. ○ Using the Euclidian algorithm: 7 = 2∙3 + 1. ○ From this equation, we get −2∙3 + 1∙7 = 1 ○ and see that −2 and 1 are Bézout coefficients of 3 and 7. ○ Hence, −2 is an inverse of 3 modulo 7. ○ Also every integer congruent to −2 modulo 7 is an inverse of 3 modulo 7 ○ i.e., 5, −9, 12, etc. • Find an inverse of 101 modulo 42620. ○ First use the Euclidian algorithm to show that gcd(101,42620) = 1. § 42620 = 45∙101 + 75 § 101 = 1∙75 + 26 § 75 = 2∙26 + 23 § 26 = 1∙23 + 3 § 23 = 7∙3 + 2 § 3 = 1∙2 + 1 § 2 = 2∙1 ○ Working Backwards § 1 = 3 − 1 ∙ 2 § 1 = 3 − 1 ∙ (23 − 7∙3) = − 1 ∙ 23 + 8 ∙ 3 § 1 = −1 ∙ 23 + 8 ∙ (26 − 1 ∙ 23) = 8 ∙ 26 − 9 ∙ 23 § 1 = 8 ∙26 − 9 ∙ (75 − 2 ∙ 26)= 26 ∙ 26 − 9 ∙ 75 § 1 = 26 ∙ (101 − 1∙75) − 9 ∙75 = 26 ∙ 101 − 35 ∙ 75 § 1 = 26 ∙ 101 − 35 ∙ (42620 − 45 ∙ 101) = − 35 ∙ 42620 + 1601 ∙ 101 ○ Bézout coefficients : − 35 and 1601 ○ Therefore 1601 is an inverse of 101 modulo 42620 Using Inverses to Solve Congruences • We can solve the congruence ax≡b (mod m) by multiplying both sides by ā. • What are the solutions of the congruence 3x ≡ 4 (mod 7). ○ We found that −2 is an inverse of 3 modulo 7 (two slides back). ○ We multiply both sides of the congruence by −2 giving ○ −2 ∙ 3x ≡ −2 ∙ 4(mod 7). ○ Because −6 ≡ 1 (mod 7) and −8 ≡ 6 (mod 7) ○ It follows that if x is a solution, then x ≡ −8 ≡ 6 (mod 7) ○ We need to determine if every x with x ≡ 6 (mod 7) is a solution. ○ Assume that x ≡ 6 (mod 7). ○ By Theorem 5 of Section 4.1, it follows that 3x ≡ 3 ∙ 6 = 18 ≡ 4 (mod 7) ○ which shows that all such x satisfy the congruence. ○ The solutions are the integers x such that x ≡ 6 (mod 7) ○ Namely, 6,13,20… and −1, − 8, − 15, … The Chinese Remainder Theorem • In the first century, the Chinese mathematician Sun-Tsu asked: ○ There are certain things whose number is unknown. ○ When divided by 3, the remainder is 2 ○ When divided by 5, the remainder is 3 ○ When divided by 7, the remainder is 2. ○ What will be the number of things? • This puzzle can be translated into the solution of the system of congruences: ○ x ≡ 2 (mod 3) ○ x ≡ 3 (mod 5) ○ x ≡ 2 (mod 7) • Theorem 2: (The Chinese Remainder Theorem) ○ Let m_1,m_2,…,m_n be pairwise relatively prime positive integers greater than one ○ Let a_1,a_2,…,a_n be arbitrary integers. ○ Then the system § x ≡ a_1 (mod m_1) § x ≡ a_2 (mod m_2) § ⋮ § x ≡ a_n (mod m_n) ○ has a unique solution modulo m=m_1 m_2⋯m_n. ○ That is, there is a solution x with 0≤x m ○ and all other solutions are congruent modulo m to this solution. • Proof ○ We’ll show that a solution exists by describing a way to construct the solution. ○ Showing that the solution is unique modulo m is Exercise 30. • Algorithm ○ To construct a solution first let M_k=m/m_k for k=1,2,…,n and m=m_1 m_2,…,m_n ○ Since gcd(m_k,M_k) = 1, there is an integer y_k, an inverse of M_k modulo m_k, such that § M_k y_k≡1 (mod m_k ) ○ Form the sum § x=a_1 M_1 y_1+a_2 M_2 y_2+a_3 M_3 y_3 ○ Note that because M_j ≡ 0 (mod m_k) whenever j≠k ○ all terms except the kth term in this sum are congruent to 0 modulo m_k . ○ Because M_k y_k ≡ 1 (mod m_k), we see that x ≡ a_k M_K y_k ≡ a_k (mod m_k), for k = 1,2,…,n. ○ Hence, x is a simultaneous solution to the n congruences. § x ≡ a_1 (mod m_1) § x ≡ a_2 (mod m_2) § ⋮ § x ≡ a_n (mod m_n) • Example ○ Consider the 3 congruences from Sun-Tsu’s problem: § x ≡ 2 (mod 3) § x ≡ 3 (mod 5) § x ≡ 2 (mod 7) ○ Let § m = 3∙ 5 ∙ 7 = 105 § M_1=m/3=35 § M_2=m/5=21 § M_3=m/7=15 ○ We see that § y_1= 2 is an inverse of M_1 = 35 modulo 3 since 35 ∙ 2 ≡ 2 ∙ 2 ≡ 1 (mod 3) § y_2= 1 is an inverse of M_2 = 21 modulo 5 since 21 ≡ 1 (mod 5) § y_3= 1 is an inverse of M_3 = 15 modulo 7 since 15 ≡ 1 (mod 7) ○ Hence, § x=a_1 M_1 y_1+a_2 M_2 y_2+a_3 M_3 y_3 § = 2 ∙ 35 ∙ 2 + 3 ∙ 21 ∙ 1 + 2 ∙ 15 ∙ 1 = 233 ≡ 23 (mod 105) ○ We have shown that 23 is the smallest positive integer that is a simultaneous solution. • Back Substitution ○ We can also solve systems of linear congruences with pairwise relatively prime moduli ○ by rewriting a congruences as an equality using Theorem 4 in Section 4.1 ○ substituting the value for the variable into another congruence, ○ and continuing the process until we have worked through all the congruences. ○ This method is known as back substitution. • Example ○ Use the method of back substitution to find all integers x such that § x ≡ 1 (mod 5) § x ≡ 2 (mod 6) § x ≡ 3 (mod 7). ○ By Theorem 4, the first congruence can be rewritten as x = 5t +1, where t is an integer. ○ Substituting into the second congruence yields 5t +1 ≡ 2 (mod 6). ○ Solving this tells us that t ≡ 5 (mod 6). ○ Using Theorem 4 again gives t = 6u + 5 where u is an integer. ○ Substituting this back into x = 5t +1, gives x = 5(6u + 5) +1 = 30u + 26. ○ Inserting this into the third equation gives 30u + 26 ≡ 3 (mod 7). ○ Solving this congruence tells us that u ≡ 6 (mod 7). ○ By Theorem 4, u = 7v + 6, where v is an integer. ○ Substituting this expression for u into x = 30u + 26 ○ tells us that x = 30(7v + 6) + 26 = 210v + 206. ○ Translating this back into a congruence we find the solution x ≡ 206 (mod 210) Fermat’s Little Theorem • Theorem 3: (Fermat’s Little Theorem) ○ If p is prime and a is an integer not divisible by p, then a^(p−1) ≡ 1 (mod p) ○ Furthermore, for every integer a we have a^p ≡ a (mod p) • This is useful in computing the remainders modulo p of large powers of integers. • Find 7^222 mod 11. ○ By Fermat’s little theorem, we know that 7^10 ≡ 1 (mod 11) ○ and so (7^10 )^k ≡ 1 (mod 11), for every positive integer k ○ Therefore, 7^222 = 7^(22×10+2)=(7^10 )^22×7^2 ≡ 1^22×49 ≡ 5 (mod 11). ○ Hence, 7^222 mod 11 = 5. Pseudoprimes • By Fermat’s little theorem n 2 is prime, where ○ 2^(n−1) ≡ 1 (mod n). • But if this congruence holds, n may not be prime. • Composite integers n such that 2^(n−1) ≡ 1 (mod n) are called pseudoprimes to the base 2. • Example: The integer 341 is a pseudoprime to the base 2. ○ 341 = 11 ∙ 31 ○ 2^340 ≡ 1 (mod 341) (see in Exercise 37) ○ We can replace 2 by any integer b ≥ 2. • Definition ○ Let b be a positive integer. ○ If n is a composite integer, and b^(n−1) ≡ 1 (mod n) ○ then n is called a pseudoprime to the base b • Given a positive integer n, such that 2^(n−1) ≡ 1 (mod n): ○ If n does not satisfy the congruence, it is composite. ○ If n does satisfy the congruence, it is either prime or a pseudoprime to the base 2. • Doing similar tests with additional bases b, provides more evidence as to whether n is prime. • Among the positive integers not exceeding a positive real number x, compared to primes • there are relatively few pseudoprimes to the base b. • For example, among the positive integers less than 〖10〗^10 there are 455,052,512 primes • but only 14,884 pseudoprimes to the base 2 Primitive Roots • Definition ○ A primitive root modulo a prime p is an integer r in Zp such that ○ every nonzero element of Zp is a power of r • Example ○ Since every element of Z11 is a power of 2, 2 is a primitive root of 11. ○ Powers of 2 modulo 11 § 2^1=2 § 2^2=4 § 2^3=8 § 2^4=5 § 2^5=10 § 2^6=9 § 2^7=7 § 2^8=3 § 2^9=6 § 2^10=1 • Example ○ Since not all elements of Z11 are powers of 3, 3 is not a primitive root of 11. ○ Powers of 3 modulo 11 § 3^1=3 § 3^2=9 § 3^3=5 § 3^4=4 § 3^5=1 § and the pattern repeats for higher powers. • Important Fact ○ There is a primitive root modulo p for every prime number p Discrete Logarithms • Suppose p is prime and r is a primitive root modulo p. • If a is an integer between 1 and p −1, that is an element of Zp, • there is a unique exponent e such that r^e = a in Zp, that is, r^e mod p = a. • Definition ○ Suppose p is prime ○ r is a primitive root modulo p ○ and a is an integer between 1 and p −1, inclusive. ○ If r^3 mod p = a and 1 ≤ e ≤ p − 1 ○ We say that e is the discrete logarithm of a modulo p to the base r and we write log_r⁡a=e • Example 1 ○ We write log_2⁡3=8 ○ Since the discrete logarithm of 3 modulo 11 to the base 2 is 8 as 28 = 3 modulo 11. • Example 2 ○ We write log_2⁡5=4 ○ since the discrete logarithm of 5 modulo 11 to the base 2 is 4 as 24 = 5 modulo 11. • There is no known polynomial time algorithm for computing the discrete logarithm • The problem plays a role in cryptography as will be discussed in Section 4.6.
Read More >>

Math 541 – 3/12

  • Mar 12, 2018
  • Shawn
  • Math 541
  • No comments yet
Theorem 35 (The Third Isomorphism Theorem) • Statement ○ Let G be a group, and H,K⊴G, where H≤K ○ Then K\/H⊴G\/H, and (G/H)⁄(K/H)≅G\/K • Note ○ K\/H≔{gH∈G/H│g∈K} ○ Also, H⊴G⇒H⊴K, and so K\/H makes sense • Recall: First Isomorphism Theorem ○ Given a homomorphism f:G→H ○ Then f ̅:G⁄ker⁡f ⟶┴≅ im(f) ○ In particular, if f is surjective, then G⁄ker⁡f ≅H • Proof ○ Check that K\/H≤G\/H § Certainly K\/H≠∅ since K≠∅ § Let k_1 H,k_2 H∈K\/H § Then k_1 H(k_2 H)^(−1)=k_1 Hk_2^(−1) H=k_1 k_2^(−1) H∈K\/H ○ Next, we show K\/H⊴G\/H § Let kH∈K\/H and gH∈G\/H § Then gHkH(gH)^(−1)=(⏟(gkg^(−1) ) H)┬(∈K)∈K\/H ○ Define a homomorphism § α:G\/H→G\/K gH↦gK ○ α is well-defined § Suppose g_1 H=g_2 H § Then g_2^(−1) g_1∈H § ⇒g_2^(−1) g_1∈K⟺g_1 K=g_2 K ○ α is surjective § If gK∈G\/K, α(gH)=gK ○ Compute ker⁡α § ker⁡α={gH∈G/H│gK=K} § ={gH∈G/H│g∈K} § =K\/H ○ By First Isomorphism Theorem § (G/H)⁄(K/H)=(G/H)⁄ker⁡α ≅im α=G\/K • Example ○ Let G=Z, K=⟨2⟩, H=⟨4⟩ ○ Then The Third Isomorphism Theorem tells us the map § Z\/4Z→Z\/2Z § a ̅→a ̅ ○ is well-defined and surjective ○ with kernel 2Z\/4Z={0 ̅,2 ̅ }⊆Z\/4Z ○ Therefore, (Z4Z⁄(2Z4Z≅Z\/2Z Proposition 36 • Statement ○ Let G,H be groups, and N⊴G ○ A homomorphism α:G→H induces a homomorphism § α ̅:G\/N→H gN↦α(g) ○ If and only if N≤ker⁡α • Proof (⟹) ○ α ̅(nN)=1_H, ∀n∈N, since homomorphisms preserve identities ○ But, α ̅(nN)=α(n) ○ Thus, α(n)=1_H,∀n∈N ○ i.e. N⊆ker⁡α ○ And N certainly meets the Subgroup Criteria ○ Therefore N≤ker⁡α • Proof (⟸) ○ We must check that α ̅:G\/N→H,gN↦α(g) is well-defined § Suppose g_1 N=g_2 N, we must check that α(g_1 )=α(g_2 ) § g_1 N=g_2 N § ⟺g_2^(−1) g_1∈N § ⇒α(g_2^(−1) g_1 )=1_H (since N≤ker⁡α) § ⟺α(g_2 )^(−1) α(g_1 )=1_H § ⟺α(g_2 )=α(g_1 ) ○ Also, α ̅ is a homomorphism § α ̅(g_1 Hg_2 H)=α ̅(g_1 g_2 H)=α(g_1 g_2 )=α(g_1 )α(g_2 )=α ̅(g_1 H) α ̅(g_2 H)
Read More >>

Math 541 – 3/9

  • Mar 12, 2018
  • Shawn
  • Math 541
  • No comments yet
Corollary 31 • Recall (Proposition 30) ○ If H,K≤G, then HK≤G⟺HK=KH • Statement ○ If H,K≤G, and either H or K is normal in G, then HK≤G • Proof ○ Without loss of generality, assume K⊴G ○ We will prove HK=KH ○ Let h∈H,k∈K ○ hk=hk(h(−1) h=⏟(h�h(−1) )┬(∈K) h∈KH⇒HK≤KH ○ kh=(h^(−1) )kh=h ⏟(h(−1) kh┬(∈K)∈HK⇒KH≤HK ○ Therefore HK=KH Theorem 32 (The First Isomorphism Theorem) • Statement ○ If f:G→H is a hormorphism, then f induces an isomorphism § f ̅:G⁄ker⁡f ⟶┴≅ im(f) § f ̅(g ker⁡f )=f(g) • Intuition ○ This is an analogue of the Rank-Nullity Theorem ○ Given vector space V,W and a linear transformation A:V→W ○ dim⁡(V⁄ker⁡A )=dim⁡〖im A〗 ○ ⇒dim⁡V−nullity A=rank A • Proof ○ f ̅ is well-defined and injective § Let g_1,g_2∈G § g_1 ker⁡f=g_2 ker⁡f § ⟺g_2^(−1) g_1∈ker⁡f § ⟺f(g_2^(−1) g_1 )=1 § ⟺f(g_2 )^(−1) f(g_1 )=1 § ⟺f(g_1 )=f(g_2 ) § ⟺f ̅(g_1 ker⁡f )=f ̅(g_2 ker⁡f ) § Thus f is well-defined and injective ○ f ̅ is surjective § Let h∈im f § Choose g∈G s.t. f(g)=h § Notice f ̅(g ker⁡f )=h ○ f ̅ is a hormorphism § If g_1 ker⁡f,g_2 ker⁡f∈G\/ker⁡f § f ̅(g_1 ker⁡f⋅g_2 ker⁡f ) § =f ̅(g_1 g_2 ker⁡f ) § =f(g_1 g_2 )=f(g_1 )f(g_2 ) § =f ̅(g_1 ker⁡f ) f ̅(g_2 ker⁡f ) § Thus, f ̅ is a hormorphism Corollary 33 • Statement ○ [G:ker⁡f ]=|im f| • Example ○ Let m,n∈Z, and assume (m,n)=1 ○ Then any homomorphism f:Z\/mZ→Z\/nZ is trivial ○ i.e. f(n ̅ )=0 ̅, ∀n ̅ • Proof ○ Let f be such a homomorphism ○ By the First Isomorphism Theorem ○ |(ZnZ⁄ker⁡f |=|im f| ○ ⇒n/|ker⁡f | =|im f|, where § n/|ker⁡f | is a divisor of n § |im f| is a divisor of m by Lagrange^′ s Theorem ○ Thus, |im f|=1, so im f={0 ̅ } • Note ○ The same proof tells us that ○ If G,H are finite groups such (|G|,|H|)=1, then ○ All homomorphism between them are trivial Theorem 34 (The Second Isomorphism Theorem) • Statement ○ Let A,B≤G, and assume B⊴G ○ Then A∩B⊴A, and AB⁄B≅A⁄(A∩B) • Intuition • Note ○ By Corollary 31, AB≤G ○ And since B⊴G, B⊴AB ○ So, AB⁄B make sense • Proof ○ We have homomorphisms § α:A→AB a↦a § β:AB→AB⁄B x↦xB ○ Set f≔βα, so § f:A→AB⁄B a↦aB ○ f(a)=1_(AB⁄B)=B⟺a∈B ○ Thus, ker⁡f=A∩B ○ Since kernels are normal, A∩B⊴A ○ The First Isomorphism Theorem gives an isomorphism ○ f ̅:A⁄(A∩B) ⟶┴≅ AB⁄B
Read More >>

Search

  • Home Page
  • Tutorials
  • Mathematics
    • Math 240 – Discrete Math
    • Math 375 – Linear Algebra
    • Math 431 – Intro to Probability
    • Math 514 – Numerical Analysis
    • Math 521 – Analysis I
    • Math 541 – Abstract Algebra
    • Math 632 – Stochastic Processes
    • Abstract Algebra @ 万门大学
    • Linear Algebra @ 万门大学
    • Category Theory
  • Computer Sciences
    • CS/ECE 252 – Intro to Computer Engr.
    • CS/ECE 352 – Digital System Fund.
    • Learn Haskell
  • Course Notes
    • AP Macroeconomics
    • AP Microeconomics
    • AP Chemistry
    • AP Statistics
    • AP Physics C: E＆M
    • AP Physics C: Mechanics
    • CLEP Psychology
  • 2048 Game
  • HiMCM 2016
  • 登峰杯 MCM

WeChat Account

Categories

  • Notes (418)
    • AP (115)
      • AP Macroeconomics (20)
      • AP Microeconomics (23)
      • AP Physics C E＆M (25)
      • AP Physics C Mechanics (28)
      • AP Statistics (19)
    • Computer Sciences (2)
    • Mathematics (300)
      • Abstract Algebra (29)
      • Category Theory (7)
      • Linear Algebra (29)
      • Math 240 (42)
      • Math 375 (71)
      • Math 514 (18)
      • Math 521 (39)
      • Math 541 (39)
      • Math 632 (26)
  • Projects (2)
  • Tutorials (11)

Archives

  • October 2019
  • May 2019
  • April 2019
  • March 2019
  • February 2019
  • December 2018
  • November 2018
  • October 2018
  • September 2018
  • July 2018
  • May 2018
  • April 2018
  • March 2018
  • February 2018
  • January 2018
  • December 2017
  • November 2017
  • October 2017
  • September 2017
  • August 2017
  • July 2017
  • June 2017

WeChat Account

Links

RobeZH's thoughts on Algorithms - Ziyi Zhang
Copyright © 2018.      
TOP