Saturday, November 23, 2013

the number of numbers less than 21 and relatively prime to 21 is

There is a famous function to compute this number, the euler totient function, when you get a chance you can look it up :) 

For now we'll compute directly since 21 is relatively small 
1, always
21/2=10 r 1 yes
21/3=7 r 0 no
21/4 => r 1 yes
21/5 yes
21/6 r 3 no
21/7 no
21/8 yes
21/9 no
21/10 yes
21/11 yes
21/12 no
21/13 yes
21/14 no
21/15 no
21/16 yes
21/17 yes
21/18 no
21/19 yes
21/20 yes
21/21 no 
so the count is...12 

:)

No comments: