MATA02H3 Lecture 9: Phi (Φ) Function and Modular Arithmetic

167 views2 pages
Verified Note
5 Feb 2019
School
Department
Course

Document Summary

Mata02 - lecture 9 - phi ( ) function and modular arithmetic (february 4th, 2019) Let"s say n" is a natural number and: n=p 1 a 1 p 2 a 2 p 3 a 3 p 4 a 4 p k a k where each p" value are distinct primes and each a" value are a positive integer. (n) = amount of numbers from 0 to (n-1) so that they are relatively prime with n". (n) = n[(p1 - 1)/p1][(p2 - 1)/p2][(p3 - 1)/p3] [(pk - 1)/pk] Determining how many numbers are relatively prime with a number, n. Ex 1: find the amount of numbers that are relatively prime with 15. Ans: first, break the number down to a product of prime numbers: n=15=3 5. Now, apply the formula: (n) = n[(p1 - 1)/p1][(p2 - 1)/p2][(p3 - 1)/p3] [(pk - 1)/pk] (15) = 15[(5 - 1)/5][(3 - 1)/3] = 15( )( ) = 8.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents