CS6515 - Exam 2 Algorithms 2025/2026
Exam Questions and Answers | 100%
Solved
Equivalence - 🧠 ANSWER ✔✔"x ≡ y (mod N) means that x/N and y/N have
the same remainder
a ≡ b (mod N) and c ≡ d (mod N) then:
a + c ≡ a + d ≡ b + c ≡ b + d (mod N)
a - c ≡ a - d ≡ b - c ≡ b - d (mod N)
a ** c ≡ a ** d ≡ b ** c ≡ b ** d (mod N)
ka ≡ kb (mod N) for any integer k
ak ≡ bk (mod N) for any natural number k
a + k ≡ b + k (mod N) for any integer k
a + b = c, then a (mod N) + b (mod N) ≡ c (mod N)
,a ** b = c, then a (mod N) ** b (mod N) ≡ c (mod N)"
Multiplicative Inverse - 🧠 ANSWER ✔✔"Exists iff x and N are relatively
prime
Is unique 1 ≤ inverse < N if it exists
z is the multiplicative inverse of x if zx ≡ 1 (mod N)
z ≡ x^(−1) (mod N)
x ≡ z^(−1) (mod N)"
Greatest Common Divisor - 🧠 ANSWER ✔✔"gcd(x,y) = largest number that
divides both x and y
gcd(x,y) = gcd(x mod y, y)"
Relatively Prime - 🧠 ANSWER ✔✔iff gcd(a,b) = 1
Fermat's Little Theorem - 🧠 ANSWER ✔✔"If p is a prime number:
a^p≡ a (mod p)
a^p-1 ≡ 1 (mod p) for 1 ≤ a ≤ p−1
a^(p-1) ≡ 1 (mod p) if a mod p ≠ 0
a^((p-1)*k) ≡ 1 (mod p) if a mod p ≠ 0 and any natural number k
, r is a prime number iff a^(r-1) ≡ 1 (mod r) for 1 ≤ a ≤ r−1"
Euler's totient function - 🧠 ANSWER ✔✔"N = pq where p and q are distinct
prime numbers
Denoted as ϕ(N)
- How many numbers from 1 to n are relatively prime to n
- 1 ≤ x ≤ N such that gcd(N,x) = 1
- ϕ(p) = p-1 where p is a prime number
- ϕ(p^2) = p(p-1) where p is a prime number
- ϕ(N) = (p-1)(q-1)"
Euler's Theorem - 🧠 ANSWER ✔✔"N = pq where p and q are distinct prime
numbers
If a,N are relatively prime:
a^ϕ(N) ≡ 1 (mod N)
a^(p-1)(q-1) ≡ 1 (mod pq)
a^ϕ(N)k ≡ 1 (mod N)
a^(p-1)(q-1)k ≡ 1 (mod pq)"
COPYRIGHT©NINJANERD 2025/2026. YEAR PUBLISHED 2025. COMPANY REGISTRATION NUMBER: 619652435. TERMS OF USE. PRIVACY
STATEMENT. ALL RIGHTS RESERVED
3
Exam Questions and Answers | 100%
Solved
Equivalence - 🧠 ANSWER ✔✔"x ≡ y (mod N) means that x/N and y/N have
the same remainder
a ≡ b (mod N) and c ≡ d (mod N) then:
a + c ≡ a + d ≡ b + c ≡ b + d (mod N)
a - c ≡ a - d ≡ b - c ≡ b - d (mod N)
a ** c ≡ a ** d ≡ b ** c ≡ b ** d (mod N)
ka ≡ kb (mod N) for any integer k
ak ≡ bk (mod N) for any natural number k
a + k ≡ b + k (mod N) for any integer k
a + b = c, then a (mod N) + b (mod N) ≡ c (mod N)
,a ** b = c, then a (mod N) ** b (mod N) ≡ c (mod N)"
Multiplicative Inverse - 🧠 ANSWER ✔✔"Exists iff x and N are relatively
prime
Is unique 1 ≤ inverse < N if it exists
z is the multiplicative inverse of x if zx ≡ 1 (mod N)
z ≡ x^(−1) (mod N)
x ≡ z^(−1) (mod N)"
Greatest Common Divisor - 🧠 ANSWER ✔✔"gcd(x,y) = largest number that
divides both x and y
gcd(x,y) = gcd(x mod y, y)"
Relatively Prime - 🧠 ANSWER ✔✔iff gcd(a,b) = 1
Fermat's Little Theorem - 🧠 ANSWER ✔✔"If p is a prime number:
a^p≡ a (mod p)
a^p-1 ≡ 1 (mod p) for 1 ≤ a ≤ p−1
a^(p-1) ≡ 1 (mod p) if a mod p ≠ 0
a^((p-1)*k) ≡ 1 (mod p) if a mod p ≠ 0 and any natural number k
, r is a prime number iff a^(r-1) ≡ 1 (mod r) for 1 ≤ a ≤ r−1"
Euler's totient function - 🧠 ANSWER ✔✔"N = pq where p and q are distinct
prime numbers
Denoted as ϕ(N)
- How many numbers from 1 to n are relatively prime to n
- 1 ≤ x ≤ N such that gcd(N,x) = 1
- ϕ(p) = p-1 where p is a prime number
- ϕ(p^2) = p(p-1) where p is a prime number
- ϕ(N) = (p-1)(q-1)"
Euler's Theorem - 🧠 ANSWER ✔✔"N = pq where p and q are distinct prime
numbers
If a,N are relatively prime:
a^ϕ(N) ≡ 1 (mod N)
a^(p-1)(q-1) ≡ 1 (mod pq)
a^ϕ(N)k ≡ 1 (mod N)
a^(p-1)(q-1)k ≡ 1 (mod pq)"
COPYRIGHT©NINJANERD 2025/2026. YEAR PUBLISHED 2025. COMPANY REGISTRATION NUMBER: 619652435. TERMS OF USE. PRIVACY
STATEMENT. ALL RIGHTS RESERVED
3
