ความเท่ากันทางเศษเหลือ, การหารลงตัว และฟังก์ชันเลขคณิต
แนะนำใหม่| English | ความหมาย |
|---|---|
| congruence/ˈkɒŋɡruːəns/ | congruence |
| totient/ˈtəʊʃənt/ | totient |
ตัดสินใจก่อนตอบคำถาม
- เครื่องจักรเครื่องหนึ่งหมุนรอบหนึ่งทุกสี่นาทีและอีกเครื่องหนึ่งทุกเจ็ดนาที. ตำแหน่งที่พร้อมกันคือปัญหา congruence, ไม่ใช่ decimal approximation
- เป้าหมายของคุณ: แก้ linear congruences โดยใช้เงื่อนไข gcd
อ่านความสัมพันธ์
- สมการ ax≡b modulo n มี solution พอดีเมื่อ d=gcd(a,n) หาร b ได้ หากทำเช่นนั้น หาร a,b,n ด้วย d เพื่อให้ได้สมการที่มี invertible coefficient มันมี one residue solution modulo n/d และ d distinct solutions modulo n การหาร coefficient แต่ทิ้ง modulus เดิมไว้โดยทั่วไปจะสูญเสีย solutions Prime factorization ให้เครื่องมือ divisibility อื่นๆ: หาก n^k ต้อง divisible by product of prime powers p^a, แต่ละ prime exponent ใน n ต้องอย่างน้อย ceil(a/k). Exponents ขั้นต่ำเหล่านี้ผลิต n ที่น้อยที่สุดที่เป็นไปได้แยกต่างหาก สำหรับ n⁴ divisible by 2⁷·3⁵, n ต้องมี 2² และ 3², ดังนั้นค่าที่น้อยที่สุดคือ 36. นี่คือ prime-exponent condition, ไม่ใช่ congruence แก้ด้วยการหาร modular
- รวม congruences ที่ coprime กับ Chinese remainder theorem
How many distinct solutions modulo 18 satisfy 6x≡12?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
gcd(6,18)=6 divides 12, so there are six solutions; after dividing the modulus too, x≡2 modulo 3.
ใช้กฎที่กำหนด
- อัลกอริทึมยูคลิดแบบขยายแสดง gcd(a,n) ในรูป ua+vn เมื่อ gcd เป็น 1, u คืออินเวอร์สของ a โมดูล n เลือกตัวแทนในช่วงที่กำหนดหลังลดรูป สำหรับ 7 และ 26, 1=15·7−4·26, ดังนั้น 15 จึงเป็นอินเวอร์สของ 7 โมดูล 26; ตรวจสอบผลคูณเพื่อจับความผิดพลาดเรื่องเครื่องหมาย
- ใช้ทฤษฎีบทของ Euler เฉพาะกับ invertible residues เท่านั้น
What is the least nonnegative x with x≡1 modulo 3 and x≡2 modulo 5?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Among 1,4,7,10,13 modulo 15, only 7 has residue 2 modulo 5.
ตรวจสอบเงื่อนไข
- สำหรับ moduli ที่ coprime m,n, Chinese remainder theorem ให้ solutions Exactly one modulo mn สำหรับแต่ละคู่ของ residue conditions. แทนที่ x=r+mk ลงใน second congruence และแก้หาค่า k. หาก moduli ไม่ได้ coprime, ค่า residual ของพวกเขาต้องตรงกัน modulo gcd(m,n); เมื่อสอดคล้องกัน, uniqueness คือ modulo least common multiple, ไม่ใช่ผลคูณ
- ใช้ prime-exponent divisibility เพื่อหา integers ที่น้อยที่สุดที่ยอมรับได้
แก้ 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.
phi(12) equals ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The coprime residues are 1,5,7,11, or use 12(1−1/2)(1−1/3)=4.
ใช้รูปแบบงาน
- ฟังก์ชัน Euler's totient phi(n) นับจำนวนเศษที่เหลือที่.action together กับ n. สำหรับตัวประกอบเฉพาะ p ที่แตกต่างกัน, phi(n)=n คูณด้วยผลคูณของ (1−1/p). ทฤษฎีบทของ Euler ให้ a^phi(n)≡1 ก็ต่อเมื่อ gcd(a,n)=1. กรณีเฉพาะคือทฤษฎีบทเล็กของ Fermat. ลดเลขชี้กำลังก็ต่อหลังจากตรวจสอบเงื่อนไขนี้แล้ว; ตัวที่ไม่ใช่ subsitute อาจกลายเป็นศูนย์ภายใต้การยกกำลังซ้ำๆ แทน
- ใช้ prime-exponent divisibility เพื่อหา integers ที่น้อยที่สุดที่ยอมรับได้
นิพจน์ a^phi(n)≡1 เป็นเท็จสำหรับ a ใดๆ ตัวอย่างเช่น 2 ไม่สามารถหา inverse ได้ modulo 8 และ 2^4 มีค่าเป็นศูนย์ modulo 8
คำตอบใดสอดคล้องกับกรณีนี้?
แก้ความเท่ากันเชิงเส้นโดยใช้เงื่อนไข GCD
x≡0 modulo 4 and x≡1 modulo 6 have a simultaneous solution.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The first condition makes x even, the second makes it odd; residues disagree modulo gcd(4,6)=2.
รักษาระยะห่าง
- ความสอดคล้อง (congruence) — ความเท่ากันของเศษเหลือเนื่องจาก modulus หารผลต่างของพวกเขาลงตัว
- totient — จำนวนของเศษที่เหลือที่.action together กับ modulus จำนวนเต็มบวก
- แก้สมการความสอดคล้องเชิงเส้นโดยใช้เงื่อนไข GCD
- รวม congruences ที่ coprime กับ Chinese remainder theorem
- ใช้ทฤษฎีบทของ Euler เฉพาะกับ invertible residues เท่านั้น
- ใช้ prime-exponent divisibility เพื่อหา integers ที่น้อยที่สุดที่ยอมรับได้
Match each term with its precise meaning in this lesson.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
The order follows the stated process; check each stage before the next.