A.6 · ความเทียบเท่า Modular การหารเหลือ และฟังก์ชันทางเลขคณิต

เตรียมสอบ GRE ระดับปริญญาตรี วัตถุประสงค์ภายในขอบเขต ETS ที่ทบทวนนี้คือการสอนต้นฉบับ ไม่ใช่การทดสอบหรือตัวทำนายคะแนนอย่างเป็นทางการ

prerequisites: Euclidean algorithm, prime factors และ modular arithmetic.

• แก้ linear congruences โดยใช้เงื่อนไข gcd
• รวม congruences ที่ coprime ด้วย Chinese remainder theorem
• ใช้ Euler's theorem กับ invertible residues เท่านั้น
• ใช้ prime-exponent divisibility เพื่อหาค่า admissible น้อยที่สุด

congruence: ความเท่ากันของ residues เพราะ modulus หารผลต่างของพวกมันได้

totient: จำนวนของ residues ที่ coprime กับ positive integer modulus

The equation ax≡b modulo n has a solution exactly when d=gcd(a,n) divides b. If it does, divide a,b,n by d to obtain an equation with an invertible coefficient. It has one residue solution modulo n/d and d distinct solutions modulo n. Dividing the coefficient but leaving the original modulus generally loses solutions. Prime factorisation gives another divisibility tool: if n^k must be divisible by a product of prime powers p^a, each prime exponent in n must be at least ceil(a/k). These minimum exponents independently produce the least positive admissible n. For n⁴ divisible by 2⁷·3⁵, n must contain 2² and 3², so the least value is 36. This is a prime-exponent condition, not a congruence solved by modular division.

extended Euclidean algorithm แสดง gcd(a,n) เป็น ua+vn. เมื่อ gcd เป็น 1, u เป็น inverse ของ a mod n. เลือก representative ในช่วงที่ต้องการหลังจาก reduction. สำหรับ 7 และ 26, 1=15·7−4·26, ดังนั้น 15 เป็น inverse ของ 7 mod 26; ตรวจสอบผลคูณเพื่อจับ error sign

สำหรับโมดูลัส m,n ที่ coprime (จำนวนร่วมตัวประกอบ prime ไม่เหมือนกัน) ทฤษฎีบทเศษเหลือจีนให้คำตอบที่แน่นอนเพียงหนึ่งค่า modulo mn สำหรับแต่ละคู่ของเงื่อนไขเศษเหลือ แทนค่า x=r+mk ลงในอสมการ congruence ตัวที่สองแล้วแก้หาค่า k หากโมดูลัสไม่ใช่ coprime ค่าเศษเหลือต้องตรงกัน modulo gcd(m,n); เมื่อสอดคล้องกัน ความไม่ซ้ำซ้อนจะอยู่ modulo least common multiple ไม่ใช่ผลคูณ

Euler's totient phi(n) นับจำนวนเศษเหลือที่เป็น coprime กับ n สำหรับตัวประกอบ prime แยกต่างหาก p, phi(n)=n คูณด้วยผลคูณของ (1−1/p) ทฤษฎีบทของ Euler บอกว่า a^phi(n)≡1 ก็ต่อเมื่อ gcd(a,n)=1 กรณีของจำนวน prime คือทฤษฎีบทเล็กของ Fermat ลดเลขชี้กำลังได้ก็ต่อเมื่อตรวจสอบเงื่อนไขนี้แล้วเท่านั้น; จำนวนที่ไม่ใช่ unit อาจกลายเป็นศูนย์ภายใต้การยกกำลังซ้ำๆ แทน

แก้ 6x≡9 modulo 15. GCD คือ 3 และหาร 9 ลงตัว หารทั้งสามปริมาณด้วยค่านี้จะได้ 2x≡3 modulo 5; Inverse ของ 2 คือ 3 ดังนั้น x≡9≡4 modulo 5. คำตอบเดิม modulo 15 คือ 4,9,14. สำหรับ x≡2 modulo 4 และ x≡3 modulo 7, เขียน x=2+4k; แล้ว 4k≡1 modulo 7, ซึ่งได้ k≡2. ดังนั้น x≡10 modulo 28.

นิพจน์ a^phi(n)≡1 เป็นเท็จสำหรับ a ใดๆ ตัวอย่างเช่น 2 ไม่สามารถหา inverse ได้ modulo 8 และ 2^4 มีค่าเป็นศูนย์ modulo 8

แก้ $8x\equiv12\pmod{20}$ ให้สมบูรณ์ หาอินเวอร์สของ 7 modulo 20 อธิบายว่าทำไมทฤษฎีบทของ Euler จึงไม่สามารถใช้แทน $2^8$ ด้วย 1 modulo 20 ได้

วิธีทำตัวอย่าง

gcd มีค่าเป็นสี่และหาร 12 ลง การหารทั้งสามตัวเลขด้วยค่านี้จะได้ $2x\equiv3\pmod5$ ดังนั้น $x\equiv4\pmod5$ modulo 20 คำตอบทั้งสี่คือ $4,9,14,19$; การแทนค่าจะได้เศษเหลือ 12 ทุกครั้ง เนื่องจาก $7\cdot3=21$, อินเวอร์สของ 7 คือ 3 แม้จะมี $\phi(20)=8$ แต่ทฤษฎีบทของ Euler ต้องการจำนวนที่เป็น unit GCD ของ 2 และ 20 คือสอง และ $2^8=256\equiv16$ ไม่ใช่ 1

Solve $x\equiv2\pmod6$, $x\equiv5\pmod9$, or prove inconsistency. State the modulus for uniqueness. Find the least positive n such that $2^5\cdot3^7$ divides $n^3$.

ตรวจสอบหลังทำแบบฝึกหัดแล้ว

residues agreement mod gcd สาม. วาง $x=2+6k$: แล้ว $6k\equiv3\pmod9$, ดังนั้น $2k\equiv1\pmod3$ และ $k\equiv2\pmod3$. ดังนั้น $x\equiv14\pmod{18}$. Modulus คือ lcm, ไม่ใช่ 54. สำหรับปัญหา divisibility, เขียน prime exponents ใน n. พวกเขาต้อง satisfy $3a\ge5$, $3b\ge7$, ดังนั้น $a\ge2$, $b\ge3$. n ที่น้อยที่สุดคือ $2^2\cdot3^3=108$; prime factors อื่นๆ สามารถทำให้มันเพิ่มขึ้นได้เท่านั้น