Let q be an odd positive integer, and let Nq denote the number of integers a such that 0<a<q/4 and gcd(a,q)=1. Show that Nq is odd if and only if q is of the form pk with k a positive integer and p a prime congruent to 5 or 7 modulo 8.
PutnamPutnam 2015Putnam number theory