MathDB

Putnam 2015 A5

Source:

December 6, 2015

PutnamPutnam 2015Putnam number theory

Problem Statement

Let

q

be an odd positive integer, and let

N_q

denote the number of integers

a

such that

0<a<q/4

and

\gcd(a,q)=1.

Show that

N_q

is odd if and only if

q

is of the form

p^k

with

k

a positive integer and

p

a prime congruent to

5

or

7

modulo

8.

Back to Problems View on AoPS