CS6515 - Exam 2 Algorithms questions and answers

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