Maths Olympiad Prep

Library / /1 of 9

Number theory Difficulty 6.0 AIME, harder Find the answer

How many integers n>1n>1 are there such that nn divides x13xx^{13}-x for every positive integer xx?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve the problem, we are tasked with finding the number of integers n>1 n > 1 such that n n divides x13x x^{13} - x for every positive integer x x .

First, observe that if nx13x n \mid x^{13} - x for every integer x x , then nx13x n \mid x^{13} - x for each x x in particular values, such as x=0,1,2,,n1 x = 0, 1, 2, \ldots, n-1 . This means that n n divides the polynomial x13x x^{13} - x evaluated at these integers.

An important observation is that the polynomial x13x x^{13} - x corresponds to the characteristic property of a finite field. Specifically, x13x0(modp) x^{13} - x \equiv 0 \pmod{p} for a prime p p implies that p13 p \mid 13 or the multiplicative order of x(modp) x \pmod{p} divides 13.

The roots of the polynomial x13x0(modn) x^{13} - x \equiv 0 \pmod{n} are precisely the elements of the finite field Zn \mathbb{Z}_n if n n is a prime power.

The polynomial x13x x^{13} - x can be factored using:
x13x=x(x121)=x(x61)(x4+x2+1). x^{13} - x = x(x^{12} - 1) = x(x^6 - 1)(x^4 + x^2 + 1).

Notice that the polynomial x(x61)(x4+x2+1) x(x^6 - 1)(x^4 + x^2 + 1) implies that n n should divide each of the factors, either directly or by induction that all prime divisors of n n must also be Fermat primes where necessary.

At this point, it is particularly significant that the prime divisors n n must satisfy n1(mod13) n \equiv 1 \pmod{13} . Therefore, we need to find all integer divisors greater than 1 of order 13. This includes small prime powers such that for each prime p p , p1(mod13) p \equiv 1 \pmod{13} , which in the case of modulo 13 implies possibly restricted to to the factor set characteristics.

Ultimately, using the properties of congruences and finite fields, we find that:

For n n such that n n divides x13x x^{13} - x for all integers x x , we have the specific minimal divisors governing congruence properties from derived direct or field characteristics:
n{2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,22,24,25,26,28,30,32,36,40,42,48,60,63,84} n \in \{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 28, 30, 32, 36, 40, 42, 48, 60, 63, 84\}

Hence, the number of such integers n n is:
31. \boxed{31}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.