10

Part of 2024 IMC

Problems(1)

Divisors of almost primes are 1 modulo Fermat primes

Source: IMC 2024, Problem 10

We say that a square-free positive integer

n

is almost prime if

n \mid x^{d_1}+x^{d_2}+\dots+x^{d_k}-kx

for all integers

x

1=d_1<d_2<\dots<d_k=n

are all the positive divisors of

n

r

is a Fermat prime (i.e. it is a prime of the form

2^{2^m}+1

m \ge 0

p

is a prime divisor of an almost prime integer

n

p \equiv 1 \pmod{r}

. Show that, with the above notation,

d_i \equiv 1 \pmod{r}

1 \le i \le k

n

is called square-free if it is not divisible by

d^2

for any integer

d>1

number theoryFermat primesprimality test