Lagrange Interpolation?

Number Theory Level 5

Find the sum of all composite integers $k$ such that for any $a_1,...,a_m \in \mathbb{Z}$ which when taken $\pmod k$ are distinct, then $∃ p(x)$ a polynomial so that the following congruence relation

$p(x) \equiv 0 \pmod k$ ,

has exactly $m$ solutions where $x \equiv a_1, a_2, ... , a_m \pmod k$ .

The answer is 4.

1 solution

Patrick Corn
May 28, 2014

If $m$ can be written as a product of two relatively prime integers $a,b \ge 2$ , then $x^2-1$ has at least four roots mod $m$ by the Chinese Remainder Theorem, so no such $m$ works. This rules out everything except for prime powers.

If $m = p^k$ where $p$ is a prime and $k \ge 2$ , then $x^2-px$ has roots $0, p, p^{k-1}, 2p^{k-1}$ . So the last two roots have to be congruent mod $p^k$ to $0$ or $p$ , which is only possible if $k = 2$ and $p = 2$ .

Finally, $m = 4$ does indeed satisfy the conditions of the problem (just check a finite, small number of cases). So the answer is $\fbox{4}$ .

@Anqi Li

Dude what do you mean by the inverted "E" ?

A Former Brilliant Member - 6 years, 3 months ago

That's mathematical shorthand for "there exists".

Calvin Lin Staff - 6 years, 3 months ago

Lagrange Interpolation?

The answer is 4.

1 solution

0 pending reports