MathDB

Divisors of almost primes are 1 modulo Fermat primes

Source: IMC 2024, Problem 10

August 8, 2024

number theoryFermat primesprimality test

Problem Statement

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

, where

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

are all the positive divisors of

n

. Suppose that

r

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

2^{2^m}+1

for an integer

m \ge 0

),

p

is a prime divisor of an almost prime integer

n

, and

p \equiv 1 \pmod{r}

. Show that, with the above notation,

d_i \equiv 1 \pmod{r}

for all

1 \le i \le k

. (An integer

n

is called square-free if it is not divisible by

d^2

for any integer

d>1

.)

Back to Problems View on AoPS