Problem 3

Find all positive integers

n

such that for any integer

k

there exists an integer

a

for which

a^3+a-k

is divisible by

n

Step 3 of 4: Primes three modulo four fail

Previous step Next step

p\equiv3\pmod4\Longrightarrow\exists a\ne b:\ a^3+a\equiv b^3+b\pmod p

Detailed analysis

For p congruent to three modulo four, let C be zero together with the quadratic residues. The values of x squared plus x plus one have exactly (p+1)/2 distinct residues, hence they are zero and all elements of C. Writing every square as (2w+1) squared shows that C would be closed under addition of three; since p is not three this would force every residue to be in C, a contradiction. Thus some x makes x squared plus x plus one a nonresidue. Using that minus the square values are precisely the nonresidues, choose nonzero a,b with a squared plus ab plus b squared equal to minus one. If a=b, replacing the pair by 2a and minus a gives a distinct pair; otherwise the factorization supplies the required collision.