AoPS - Problem

Processing math: 65%

Problem

Source: 2018 Saudi Arabia GMO TST II p1

Tags: number theory, greatest common divisor, GCD

parmenides51

31.07.2020 18:49

Let $n$ be an odd positive integer with $n > 1$ and let $a_1, a_2,... , a_n$ be positive integers such that gcd $(a_1, a_2,... , a_n) = 1$ . Let $d$ = gcd $(a_1^n + a_1\cdot a_2 \cdot \cdot \cdot a_n, a_2^n + a_1\cdot a_2 \cdot \cdot \cdot a_n, ... , a_n^n + a_1\cdot a_2 \cdot \cdot \cdot a_n)$ . Show that the possible values of $d$ are $d = 1, d = 2$

Jjesus

20.12.2020 19:46

any ideas?

Zezohabibullah

20.05.2022 22:05

The case $d=1$ is achievable at $(a_{1},a_{2},...,a_{n})=(2,1,1,...,1),$ so let $d>1$ . Let $P=a_{1}a_{2}\cdots a_{n},$ notice that $a_{1}^{n}\equiv a_{2}^{n}\equiv ...\equiv a_{n}^{n}\equiv -P\;(mod\;d)$ so $\gcd (d,P)=1$ (otherwise $p|\gcd (a_{1},a_{2},...,a_{n})$ for some prime divisor $p$ of $d$ ). Now $P^{n}\equiv \prod _{k=1}^{n}a_{k}^{n}\equiv (-P)^{n}\equiv -P^{n}\;(mod\; d)$ Which immediately gives $d=2$ , and it is achievable at $a_{1}=a_{2}=...=a_{n}$ . So we are done

Newmaths

29.02.2024 18:06

The same as 2017 ELMO.