GCD = 1

For a positive integer n>2,n>2, what can we say about the number of positive integers less than nn that are relatively prime to nn (that is, their GCD is 1)?

Hint: A useful property of the Greatest Common Divisor function is gcd(a,b)=gcd(a,ab);\gcd(a,b) = \gcd(a,a-b); e.g., gcd(10,8)=gcd(10,2)=2.\gcd(10,8) = \gcd(10,2) = 2.

×

Problem Loading...

Note Loading...

Set Loading...