MATA02H3 Lecture Notes - Lecture 18: Euclidean Algorithm, Linear Combination, Prime Number

• School: UTSC
• Department: Mathematics
• Course: MATA02H3
• Professor: Sophie Chrysostomou

Document Summary

Mata02 - lecture 18 - solutions to powers in modules, euclidean arithmetic, fermat"s. Question : how do you find the solutions of. K a: check if p" is a prime number, check if a 0 mod p, check if k" and (p-1) are relatively prime. = x mod p. this can be re-written as x k = a mod p. = x mod p has a solution x = a m mod p. You have to use euclidean algorithm (ea) to find the integers m" & " such that: 1 = mk - (p-1) mk = 1 + (p-1) a mk = a 1+ (p-1) = a 1 a (p-1) = a 1 (a p-1 ) = a mod p. Based on this, fermat" theorem states that: if p" is a prime and a 0 mod p, a p = 1 mod p. based on this, (a m ) k = a mod p. therefore,