คณิตศาสตร์ไม่ต่อเนื่อง: ชุดสรุปเร่งรัด

สรุปสูตร ขั้นตอนวิธีทำที่สำคัญของทุกหัวข้อ และโจทย์ฝึก 8 ข้อ พร้อมเฉลยละเอียดไว้ท้ายเล่ม

โจทย์ใหม่กลับไปที่รายวิชา

ในหน้าต่างพิมพ์ ให้เลือก “บันทึกเป็น PDF” เพื่อเก็บสำเนาไว้ในอุปกรณ์ของคุณ

1สูตรและวิธีทำ

ตรรกศาสตร์ประพจน์และการพิสูจน์

แถวของตารางค่าความจริง
2ⁿ
นัยสำคัญ (ถ้า–แล้ว)
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
นิเสธของนัย
¬(p → q) ≡ p ∧ ¬q
เงื่อนไขสองทาง
p ↔ q ≡ (p → q) ∧ (q → p)
กฎของเดอมอร์แกน
¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
กฎการแจกแจง
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
นิเสธของตัวบ่งปริมาณ
¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
โมดัสโพเนนส์ โมดัสโทลเลนส์
p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

วิธีการ

  1. นับจำนวนตัวแปรที่ต่างกัน ตารางค่าความจริงมี 2ⁿ แถว โดยเริ่มจากแถวที่ทุกตัวเป็น 1
  2. ให้ทุกประพจน์ย่อยมีคอลัมน์ของตัวเอง และเติมคอลัมน์จากด้านในออกมาด้านนอก
  3. ใช้กฎของตัวเชื่อมแต่ละตัว: → เป็น 0 เฉพาะเมื่อ 1 → 0 และ ↔ เป็น 1 เมื่อทั้งสองข้างมีค่าเท่ากัน
  4. สำหรับความสมมูล ให้เปรียบเทียบคอลัมน์สุดท้ายทีละแถว สำหรับการอ้างเหตุผล ให้ดูเฉพาะแถวที่ทุกสมมติฐานเป็น 1
  5. การหานิเสธของข้อความที่มีตัวบ่งปริมาณ ให้ย้าย ¬ เข้าไปด้านใน สลับ ∀ กับ ∃ และใส่นิเสธให้สูตรด้านใน

เซต ความสัมพันธ์ และฟังก์ชัน

สองเซต
|A ∪ B| = |A| + |B| − |A ∩ B|
สามเซต
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
ผลต่างและคอมพลีเมนต์
A − B = A ∩ B′, |A′| = |U| − |A|
เพาเวอร์เซตและผลคูณคาร์ทีเซียน
|𝒫(A)| = 2|A|, |A × B| = |A|·|B|
เซตย่อยขนาด k
C(n, k) = n!/(k!(n − k)!)
ฟังก์ชัน A → B
nᵐ; injective n!/(n − m)!; surjective Σ (−1)ᵏ C(n, k)(n − k)ᵐ
ความสัมพันธ์บน n สมาชิก
2n²; reflexive 2n² − n; symmetric 2n(n+1)/2
ฟังก์ชันประกอบ
(g ∘ f)(x) = g(f(x))

วิธีการ

  1. วาดแผนภาพเวนน์แล้วพิจารณาทีละบริเวณว่าบริเวณใดเป็นของนิพจน์เซต
  2. สำหรับโจทย์การนับ ให้เติมบริเวณจากตรงกลางออกไป คือทุกเซตก่อน แล้วเป็นคู่ จากนั้นเป็นเซตเดี่ยว และสุดท้ายคือด้านนอก
  3. ใช้หลักการเพิ่มเข้า–ตัดออกเพื่อตรวจสอบ: |A ∪ B| = |A| + |B| − |A ∩ B|
  4. สำหรับความสัมพันธ์ ให้ทดสอบสมบัติแต่ละข้อกับทุกคู่ และยกตัวอย่างค้านหนึ่งตัวอย่างเมื่อสมบัตินั้นไม่เป็นจริง
  5. สำหรับฟังก์ชัน ให้นับลูกศรที่ชี้เข้าแต่ละสมาชิกของ B ถ้ามากที่สุดหนึ่งลูกคือฟังก์ชันหนึ่งต่อหนึ่ง ถ้าอย่างน้อยหนึ่งลูกคือฟังก์ชันทั่วถึง

ทฤษฎีกราฟ

เล็มมาการจับมือ
Σ deg(v) = 2|E|
กราฟบริบูรณ์
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
กราฟปรกติ
|E| = n·k/2
ต้นไม้และป่า
|E| = n − 1, |E| = n − c
ใบของต้นไม้
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
ออยเลอร์
วงจร: ดีกรีเป็นคู่ทุกจุดยอด; ทางเดิน: มีดีกรีคี่พอดี 2 จุดยอด
วงจรแฮมิลตันใน Kn
(n − 1)!/2
การปรับค่าของไดก์สตรา
d(v) = min(d(v), d(u) + w(u, v))
วอล์กความยาว L
(Mᴸ)ij

วิธีการ

  1. เขียนดีกรีของทุกจุดยอด ผลบวกของดีกรีเท่ากับสองเท่าของจำนวนเส้นเชื่อม
  2. สำหรับโจทย์ออยเลอร์ ให้ตรวจว่ากราฟเชื่อมโยงกัน และนับจุดยอดที่มีดีกรีคี่
  3. สำหรับต้นไม้ ให้ใช้ว่ามี n − 1 เส้นเชื่อม และเล็มมาการจับมือ
  4. สำหรับไดก์สตรา ให้เก็บตารางระยะทางชั่วคราว และยืนยันจุดยอดที่ยังไม่ยืนยันซึ่งมีค่าน้อยที่สุดในแต่ละรอบ
  5. สำหรับต้นไม้ทอดข้ามค่าน้อยที่สุด ให้เรียงเส้นเชื่อมตามน้ำหนักและข้ามทุกเส้นที่ทำให้เกิดวัฏจักร (ครัสคัล) หรือขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น (พริม)

ทฤษฎีจำนวนและเลขคณิตมอดูลาร์

การหารที่มีเศษ
a = q·n + r, 0 ≤ r < n
ยูคลิด
gcd(a, b) = gcd(b, a mod b)
ตัวคูณร่วมน้อย
lcm(a, b) = a·b/gcd(a, b)
อินเวอร์ส
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
ความสอดคล้องเชิงเส้น
a·x ≡ b → x ≡ a⁻¹·b (mod n)
ฟังก์ชันโทเทียนต์ของออยเลอร์
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
แฟร์มา
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

วิธีการ

  1. ลดทุกจำนวนมอดูโล n ก่อน เศษจะอยู่ระหว่าง 0 ถึง n − 1
  2. สำหรับ ห.ร.ม. ให้หารซ้ำด้วยขั้นตอนวิธีของยูคลิด เศษที่ไม่เป็นศูนย์ตัวสุดท้ายคือ ห.ร.ม.
  3. สำหรับตัวผกผัน ให้ทำขั้นตอนวิธีแบบขยาย และเก็บสัมประสิทธิ์ของ a ถ้าเป็นลบให้บวก n
  4. แก้ a·x ≡ b โดยคูณด้วย a⁻¹ รวมสองความสอดคล้องโดยเขียน x = r₁ + m₁k
  5. สำหรับเลขยกกำลัง ให้เขียนเลขชี้กำลังเป็นเลขฐานสองแล้วยกกำลังสองซ้ำ ใน RSA จะได้ d = e⁻¹ mod φ(n) โดย φ(n) = (p − 1)(q − 1)

2โจทย์ฝึก

1.ตรรกศาสตร์ประพจน์และการพิสูจน์ปานกลาง
pqrr ∨ q(r ∨ q) ∨ p¬((q → p) ∧ ¬r) ∧ ((r ∨ q) ∨ p)111?110?101?100?011?010?001?000?

ในตารางค่าความจริง 8 แถวของ ¬((q → p) ∧ ¬r) ∧ ((r ∨ q) ∨ p) มีกี่แถวที่เป็นจริง เรียกจำนวนนี้ว่า N

¬((q → p) ∧ ¬r) ∧ ((r ∨ q) ∨ p)
N =
2.ตรรกศาสตร์ประพจน์และการพิสูจน์ยาก
∀x ∀y ¬R(x, y)∃x ∃y ¬R(x, y)∀x ∃y ¬R(x, y)∃x ∀y ¬R(x, y)

ประโยคใดสมมูลกับ ¬∃x ∀y R(x, y) เมื่อย้ายนิเสธเข้าด้านในสุด ให้คลิกประโยคนั้น

¬∃x ∀y R(x, y)
  1. 1∀x ∀y ¬R(x, y)
  2. 2∃x ∃y ¬R(x, y)
  3. 3∀x ∃y ¬R(x, y)
  4. 4∃x ∀y ¬R(x, y)
3.เซต ความสัมพันธ์ และฟังก์ชันปานกลาง
123

R = {(1, 2), (1, 3), (2, 2), (3, 2)} เป็นความสัมพันธ์บน {1, 2, 3} ต้องเพิ่มคู่อันดับให้ R อย่างน้อยกี่คู่ k เพื่อให้เป็นความสัมพันธ์สะท้อน

R = {(1, 2), (1, 3), (2, 2), (3, 2)}
k =
4.เซต ความสัมพันธ์ และฟังก์ชันยาก
AB1234abcdหนึ่งต่อหนึ่ง แต่ไม่ทั่วถึงทั่วถึง แต่ไม่หนึ่งต่อหนึ่งหนึ่งต่อหนึ่งทั่วถึงไม่ใช่ทั้งสองอย่าง

แผนภาพลูกศรแสดงฟังก์ชัน f: A → B โดย A = {1, 2, 3, 4} และ B = {a, b, c, d} ให้คลิกคำอธิบายที่ตรงกับ f

f = {(1, a), (2, b), (3, d), (4, c)}
  1. 1หนึ่งต่อหนึ่ง แต่ไม่ทั่วถึง
  2. 2ทั่วถึง แต่ไม่หนึ่งต่อหนึ่ง
  3. 3หนึ่งต่อหนึ่งทั่วถึง
  4. 4ไม่ใช่ทั้งสองอย่าง
5.ทฤษฎีกราฟปานกลาง

กราฟเชื่อมโยงมี 14 จุดยอดและ 21 เส้นเชื่อม ต้องเอาเส้นเชื่อมออกกี่เส้น k เพื่อให้เหลือต้นไม้ทอดข้าม

|V| = 14|E| = 21
k =
6.ทฤษฎีกราฟยาก
1017611451541271119ABCDEFG

ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุด ให้คลิกเส้นเชื่อมที่เพิ่มเป็นเส้นหมายเลข 3 เส้นที่ถูกข้ามไม่นับ

k = 3
  1. 1เส้นเชื่อม AB
  2. 2เส้นเชื่อม AC
  3. 3เส้นเชื่อม BC
  4. 4เส้นเชื่อม BD
  5. 5เส้นเชื่อม CE
  6. 6เส้นเชื่อม DE
  7. 7เส้นเชื่อม DF
  8. 8เส้นเชื่อม EF
  9. 9เส้นเชื่อม GB
  10. 10เส้นเชื่อม GC
  11. 11เส้นเชื่อม GD
  12. 12เส้นเชื่อม GE
7.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ปานกลาง

จงหาตัวผกผันของ 3 มอดูโล 17: จำนวน x ที่ 0 < x < 17 และ 3·x ≡ 1 (mod 17)

a = 3n = 17
3−1 mod 17 =
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ยาก

ใช้การยกกำลังสองซ้ำเพื่อหา 53163 mod 86

a = 53k = 163n = 86
53163 mod 86 =

3สารละลาย

1.ตรรกศาสตร์ประพจน์และการพิสูจน์

คำตอบ: N = 5

ตารางค่าความจริง: สูตรที่มีตัวแปรต่างกัน n ตัวมี 2ⁿ แถว หนึ่งแถวต่อทุกชุดของค่าความจริง (1 = จริง, 0 = เท็จ) ทำจากด้านในออกมาและให้ทุกประพจน์ย่อยมีคอลัมน์ของตัวเอง ¬a กลับค่า a ∧ b เป็น 1 เฉพาะเมื่อทั้งสองเป็น 1 a ∨ b เป็น 0 เฉพาะเมื่อทั้งสองเป็น 0 a → b เป็น 0 เฉพาะเมื่อ a = 1 และ b = 0 a ↔ b เป็น 1 เมื่อทั้งสองข้างเท่ากัน

ตารางค่าความจริงทีละแถว

p = 1, q = 1, r = 1: q → p = 1, ¬r = 0, (q → p) ∧ ¬r = 0, ¬((q → p) ∧ ¬r) = 1, r ∨ q = 1, (r ∨ q) ∨ p = 1, ¬((q → p) ∧ ¬r) ∧ ((r ∨ q) ∨ p) = 1
p = 1, q = 1, r = 0: q → p = 1, ¬r = 1, (q → p) ∧ ¬r = 1, ¬((q → p) ∧ ¬r) = 0, r ∨ q = 1, (r ∨ q) ∨ p = 1, ¬((q → p) ∧ ¬r) ∧ ((r ∨ q) ∨ p) = 0
p = 1, q = 0, r = 1: q → p = 1, ¬r = 0, (q → p) ∧ ¬r = 0, ¬((q → p) ∧ ¬r) = 1, r ∨ q = 1, (r ∨ q) ∨ p = 1, ¬((q → p) ∧ ¬r) ∧ ((r ∨ q) ∨ p) = 1
p = 1, q = 0, r = 0: q → p = 1, ¬r = 1, (q → p) ∧ ¬r = 1, ¬((q → p) ∧ ¬r) = 0, r ∨ q = 0, (r ∨ q) ∨ p = 1, ¬((q → p) ∧ ¬r) ∧ ((r ∨ q) ∨ p) = 0
p = 0, q = 1, r = 1: q → p = 0, ¬r = 0, (q → p) ∧ ¬r = 0, ¬((q → p) ∧ ¬r) = 1, r ∨ q = 1, (r ∨ q) ∨ p = 1, ¬((q → p) ∧ ¬r) ∧ ((r ∨ q) ∨ p) = 1
p = 0, q = 1, r = 0: q → p = 0, ¬r = 1, (q → p) ∧ ¬r = 0, ¬((q → p) ∧ ¬r) = 1, r ∨ q = 1, (r ∨ q) ∨ p = 1, ¬((q → p) ∧ ¬r) ∧ ((r ∨ q) ∨ p) = 1
p = 0, q = 0, r = 1: q → p = 1, ¬r = 0, (q → p) ∧ ¬r = 0, ¬((q → p) ∧ ¬r) = 1, r ∨ q = 1, (r ∨ q) ∨ p = 1, ¬((q → p) ∧ ¬r) ∧ ((r ∨ q) ∨ p) = 1
p = 0, q = 0, r = 0: q → p = 1, ¬r = 1, (q → p) ∧ ¬r = 1, ¬((q → p) ∧ ¬r) = 0, r ∨ q = 0, (r ∨ q) ∨ p = 0, ¬((q → p) ∧ ¬r) ∧ ((r ∨ q) ∨ p) = 0

นับแถวที่มีค่าเป็น 1

¬((q → p) ∧ ¬r) ∧ ((r ∨ q) ∨ p): 1, 0, 1, 0, 1, 1, 1, 0
N = 5

คำตอบ

N = 5
2.ตรรกศาสตร์ประพจน์และการพิสูจน์

คำตอบ: ∀x ∃y ¬R(x, y)

ตัวบ่งปริมาณและการอ้างเหตุผล: ¬∀x P(x) ≡ ∃x ¬P(x) และ ¬∃x P(x) ≡ ∀x ¬P(x) ย้ายนิเสธเข้าด้านใน สลับทุกตัวบ่งปริมาณที่นิเสธผ่าน และใส่นิเสธให้สูตรด้านในด้วยกฎของประพจน์ เช่น ¬(a → b) ≡ a ∧ ¬b การอ้างเหตุผลสมเหตุสมผลเมื่อบทสรุปเป็น 1 ในทุกแถวที่สมมติฐานทั้งหมดเป็น 1 แถวเดียวที่สมมติฐานเป็นจริงแต่บทสรุปเป็นเท็จคือตัวอย่างค้านและแสดงว่าการอ้างเหตุผลนั้นไม่สมเหตุสมผล

ย้ายนิเสธเข้าด้านใน

¬∃x ∀y R(x, y) ≡ ∀x ∃y ¬R(x, y)

คำตอบ

∀x ∃y ¬R(x, y)

ตัวเลือกอื่นอาจคงตัวบ่งปริมาณไว้ไม่เปลี่ยน เปลี่ยนลำดับของตัวบ่งปริมาณ หรือใส่นิเสธให้สูตรด้านในผิด

3.เซต ความสัมพันธ์ และฟังก์ชัน

คำตอบ: k = 2

ความสัมพันธ์: ความสัมพันธ์ R บนเซต X คือเซตของคู่อันดับ (x, y) R สะท้อนเมื่อ (x, x) ∈ R สำหรับทุก x ใน X; สมมาตรเมื่อ (x, y) ∈ R มี (y, x) ∈ R มาด้วยเสมอ; ปฏิสมมาตรเมื่อ (x, y) และ (y, x) อยู่ใน R ทั้งคู่เฉพาะเมื่อ x = y; และแพร่ผ่านเมื่อ (x, y) และ (y, z) ใน R บังคับให้ (x, z) ∈ R ความสัมพันธ์สมมูลคือความสัมพันธ์ที่สะท้อน สมมาตร และแพร่ผ่าน และแบ่ง X เป็นคลาสที่ไม่ซ้อนกัน

คู่ที่ต้องเพิ่ม

{(1, 1), (3, 3)}

นับ

k = 2

คำตอบ

k = 2
4.เซต ความสัมพันธ์ และฟังก์ชัน

คำตอบ: หนึ่งต่อหนึ่งทั่วถึง

ฟังก์ชันและการนับ: ฟังก์ชัน f: A → B ให้สมาชิกทุกตัวของ A มีภาพใน B เพียงหนึ่งตัวพอดี f เป็นหนึ่งต่อหนึ่ง (injective) เมื่อสมาชิกต่างกันมีภาพต่างกัน ทั่วถึง (surjective) เมื่อสมาชิกทุกตัวของ B เป็นภาพ และหนึ่งต่อหนึ่งทั่วถึง (bijective) เมื่อเป็นจริงทั้งสองอย่าง เมื่อ |A| = m และ |B| = n มี nᵐ ฟังก์ชัน ฟังก์ชันหนึ่งต่อหนึ่ง n!/(n − m)! ฟังก์ชัน (m ≤ n) และฟังก์ชันทั่วถึง Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ ฟังก์ชันโดยหลักการเพิ่มเข้า–ตัดออก |𝒫(A)| = 2ᵐ และ |A × B| = m·n

หนึ่งต่อหนึ่งหรือไม่

สมาชิกทุกตัวของ B ถูกชี้ไม่เกินหนึ่งครั้ง → หนึ่งต่อหนึ่ง

ทั่วถึงหรือไม่

สมาชิกทุกตัวของ B ถูกชี้ → ทั่วถึง

คำตอบ

หนึ่งต่อหนึ่งทั่วถึง

คำตอบ

หนึ่งต่อหนึ่งทั่วถึง
5.ทฤษฎีกราฟ

คำตอบ: k = 8

ออยเลอร์ แฮมิลตัน และต้นไม้: กราฟเชื่อมโยงมีวงจรออยเลอร์ (ผ่านทุกเส้นเชื่อมครั้งเดียวและกลับจุดเริ่มต้น) เมื่อทุกจุดยอดมีดีกรีคู่ และมีทางเดินออยเลอร์ที่ไม่ใช่วงจรเมื่อมีจุดยอดดีกรีคี่พอดีสองจุด ทางเดินนั้นไปจากจุดยอดคี่จุดหนึ่งถึงอีกจุดหนึ่ง วงจรแฮมิลตันผ่านทุกจุดยอดครั้งเดียว Kn มีวงจรแบบนี้ (n − 1)!/2 วงจร ต้นไม้ที่มี n จุดยอดมี n − 1 เส้นเชื่อม และกราฟเชื่อมโยงที่มี m เส้นเชื่อมจะเหลือต้นไม้ทอดข้ามหลังเอาเส้นเชื่อมออก m − n + 1 เส้น

เส้นเชื่อมของต้นไม้ทอดข้าม

14 − 1 = 13

เส้นเชื่อมที่ต้องเอาออก

k = 21 − 13 = 8

คำตอบ

k = 8
6.ทฤษฎีกราฟ

คำตอบ: เส้นเชื่อม DE

เส้นทางที่สั้นที่สุดและต้นไม้ทอดข้าม: ขั้นตอนวิธีของไดก์สตรายืนยันหนึ่งจุดยอดต่อรอบ: จุดยอดที่ยังไม่ยืนยันซึ่งมีระยะทางชั่วคราวน้อยที่สุด ระยะทางของมันเป็นค่าสุดท้ายแล้ว และเพื่อนบ้าน v ทุกจุดได้ d(v) = min(d(v), d(u) + w(u, v)) ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุดโดยเลือกเส้นเชื่อมจากเบาไปหนักและข้ามเส้นที่ทำให้เกิดวัฏจักร ขั้นตอนวิธีของพริมขยายต้นไม้หนึ่งต้นจากจุดยอดเริ่มต้นโดยเพิ่มเส้นเชื่อมที่เบาที่สุดที่ออกจากต้นไม้เสมอ ต้นไม้ทอดข้ามที่มี n จุดยอดมี n − 1 เส้นเชื่อม

ขั้นตอนวิธีของครัสคัล

1. BD (1)
2. EF (4)
3. DE (5)
4. BC (6)
5. GC (7)
6. AB (10)

เส้นเชื่อมหมายเลข 3

DE

คำตอบ

เส้นเชื่อม DE
7.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์

คำตอบ: 3−1 mod 17 = 6

ตัวผกผันและความสอดคล้อง: a มีตัวผกผันมอดูโล n เมื่อ gcd(a, n) = 1 เท่านั้น ขั้นตอนวิธีของยูคลิดแบบขยายเขียน 1 = s·n + t·a แล้ว a⁻¹ ≡ t (mod n) ความสอดคล้อง a·x ≡ b (mod n) ที่ gcd(a, n) = 1 มีคำตอบ x ≡ a⁻¹·b ความสอดคล้องสองข้อ x ≡ r₁ (mod m₁) และ x ≡ r₂ (mod m₂) ที่มอดูลัสเป็นจำนวนเฉพาะสัมพัทธ์กันมีคำตอบเดียวมอดูโล m₁·m₂ (ทฤษฎีบทเศษเหลือของจีน) φ(n) ของออยเลอร์นับจำนวนตั้งแต่ 1 ถึง n ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n: φ(n) = n·∏(1 − 1/p)

ขั้นตอนวิธีของยูคลิดแบบขยาย

เศษ r แต่ละตัวเขียนเป็น r ≡ t·3 (mod 17)

r = 17, t = 0
r = 3, q = 5, t = 1
r = 2, q = 1, t = −5
r = 1, q = 2, t = 6

อินเวอร์ส

1 ≡ 6·3 (mod 17)
x = 6
ตรวจสอบ: 3·6 = 18 = 1·17 + 1

คำตอบ

3−1 mod 17 = 6
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์

คำตอบ: 53163 mod 86 = 31

เลขยกกำลังมอดูลาร์และ RSA: คำนวณ aᵏ mod n ด้วยการยกกำลังสองซ้ำ: เขียน k เป็นเลขฐานสอง ยกกำลังสอง ลดค่าหลังทุกขั้นตอน และคูณเลขยกกำลังที่บิตเป็น 1 แฟร์มา: aᵖ⁻¹ ≡ 1 (mod p) สำหรับจำนวนเฉพาะ p ที่หาร a ไม่ลงตัว ดังนั้นลดเลขชี้กำลังมอดูโล p − 1 ได้ RSA: เลือกจำนวนเฉพาะ p และ q, n = p·q และ φ(n) = (p − 1)(q − 1) เลขชี้กำลังสาธารณะ e เป็นจำนวนเฉพาะสัมพัทธ์กับ φ(n) และเลขชี้กำลังส่วนตัวคือ d = e⁻¹ mod φ(n) เข้ารหัสด้วย c = mᵉ mod n และถอดรหัสด้วย m = cᵈ mod n

เลขชี้กำลังฐานสอง

163 = 101000112 = 128 + 32 + 2 + 1

การยกกำลังสองซ้ำ

531 ≡ 53 (mod 86)
532 ≡ 57 (mod 86)
534 ≡ 67 (mod 86)
538 ≡ 17 (mod 86)
5316 ≡ 31 (mod 86)
5332 ≡ 15 (mod 86)
5364 ≡ 53 (mod 86)
53128 ≡ 57 (mod 86)

คูณเลขยกกำลังที่ต้องใช้

53163 ≡ 53·57·15·57 ≡ 31 (mod 86)

คำตอบ

53163 mod 86 = 31

ExamProblems · examproblems.com/courses/discrete-mathematics