MATA02H3 Lecture Notes - Lecture 1: Prime Number
136 views2 pages
![MATA02H3 Full Course Notes](https://new-docs-thumbs.oneclass.com/doc_thumbnails/list_view/2318854-class-notes-ca-utsc-mata-02h3-lecture3.jpg)
12
MATA02H3 Full Course Notes
Verified Note
12 documents
Document Summary
First find powers like: 31, 32, 34, 38, 316, 332, - - - -, so on. Successive squaring can do this, for prime and composite modulus. 32 (31)2 (mod 24) 9 (mod 24) 34 (32)2 (mod 24) (9)2 (mod 24) 81 (mod 24) 9 (mod 24) 38 (34)2 (mod 24) (9)2 (mod 24) 81 (mod 24) 9 (mod 24) 316 (38)2 (mod 24) (9)2 (mod 24) 81 (mod 24) 9 (mod 24) 323 9 x 9 x 9 x 3 (mod 24) Fermat"s little theorem (for prime modulus only) a (p 1) 1 (mod p) for any a which is nonzero and non multiple of prime p. 32 (31)2 (mod 61) 9 (mod 61) 34 (32)2 (mod 61) (9)2 (mod 61) 81 (mod 61) 20 (mod 61) 38 (34)2 (mod 61) (20)2 (mod 61) 400 (mod 61) 34 (mod 61) 316 (38)2 (mod 61) (34)2 (mod 61) 1156 (mod 61) 58 (mod 61) [ -3 (mod 61)]