Let $A$ be an infinite set of positive integers. Find all natural numbers $n$ such that for each $a \in A$, \[a^n + a^{n-1} + \cdots + a^1 + 1 \mid a^{n!} + a^{(n-1)!} + \cdots + a^{1!} + 1.\] Proposed by Milos Milosavljevic
Problem
Source: Serbia NMO 2010 problem 3
Tags: number theory unsolved, number theory
11.03.2011 09:49
$Q(x)=1+x+\cdots +x^n$ and $P(x)=1+x^{1!}+\cdots+x^{n!}$. $P(x)=Q(x)T(x)+R(x)$, with $\deg R<\deg Q = n$. Since for infinitely many positive integers $n$ we have $Q(n)\mid R(n)$, but $ |Q(n)| >|R(n)|$ for large enough $n$, it follows $R(n)=0$ for infinitely many large enough $n$, thus $R(x)$ is identically null. Thus $1+x+\cdots +x^n\mid 1+x^{1!}+\cdots +x^{n!}$. $1+x+...+x^n=0\Longrightarrow x^{n+1}=0$ $\Longrightarrow 1+x+...+x^n\mid 1+x^{1(mod(n+1))}+...+x^{n!(mod(n+1))}$ $\Longrightarrow \{ 1,2,...,n\} \equiv \{1,2!,...,n!\} (mod (n+1))$ $\Longrightarrow$ $n+1$ is prime. $n+1=p$ but $1\equiv 1!(mod p)$ and $(n-1)!=(p-2)!\equiv 1(mod p) \Longrightarrow n-1=1,0\Longrightarrow n=1,2$
01.06.2011 04:14
The following is also true: If there exists a positive integer $a>1$ such that \[ a^{n}+a^{n-1}+\cdots+a^{1}+1\mid a^{n!}+a^{(n-1)!}+\cdots +a^{1!}+1 \] then $n=1$ or $2$.
11.01.2014 08:46
jgnr wrote: The following is also true: If there exists a positive integer $a>1$ such that \[ a^{n}+a^{n-1}+\cdots+a^{1}+1\mid a^{n!}+a^{(n-1)!}+\cdots +a^{1!}+1 \] then $n=1$ or $2$. How to prove this?
11.01.2014 14:42
Goutham wrote: Let $A$ be an infinite set of positive integers. Find all natural numbers $n$ such that for each $a \in A$, \[a^n + a^{n-1} + \cdots + a^1 + 1 \mid a^{n!} + a^{(n-1)!} + \cdots + a^{1!} + 1.\] Proposed by Milos Milosavljevic If $n>2$ If $n+1$ composite number! Τhen there is a prime $p$ so as.. $p|a^n + a^{n-1} + \cdots + a^1 + 1$ (1) $p|a^{n!} + a^{(n-1)!} + \cdots + a^{1!} + 1$ (2) From (1) $p|a^{n+1}-1$ (3) so $p|a^{n!}-1$ and from (2) must... (because $n+1|n!$ $p|a^{(n-1)!} + \cdots + a^{1!} + 2$ (3) Also because of (3) and $n>2$ must.. $p|a^{n+1}-1$ (3) $p|a^{(n-1)!}-1$ (4) (because $n+1|(n-1)!$) From (2),(4) must be.. $p|a^{n!} + a^{(n-2)!} + \cdots + a^{1!} + 2$ (5) From (3),(5) we have.. $p|a^{n!}-a^{(n-1)!}$ $p|a-1$ for every natural $a$ and from (1) $p|n+1$ but if $p|a-1$ and $p|n+1$ and from (2) $p=n+1$ contradiction so $n+1$ is a prime ....and continue... (*Thanks i corrected the mistakes.)
11.01.2014 15:34
Αρχιμήδης 6 wrote: Goutham wrote: Let $A$ be an infinite set of positive integers. Find all natural numbers $n$ such that for each $a \in A$, \[a^n + a^{n-1} + \cdots + a^1 + 1 \mid a^{n!} + a^{(n-1)!} + \cdots + a^{1!} + 1.\] Proposed by Milos Milosavljevic (because $n+1|n!$ (because $n+1|(n-1)!$) These are not true if $ n+1 $ is a prime. Αρχιμήδης 6 wrote: $p|a-1$ for every natural $a$ so for $a=2$ $p=1$ and there is not solutions for $a=2$ We don't know whether $ 2 $ is contained in $ A $ or not. Your solution is completely wrong.
23.03.2017 20:29
This quite resembles in terms of ideas IMO 2002 3. Lemma:if $P(n)\mid Q(n)$ for infinitely many than we have $P\mid R$ in $\mathbb{Z}[X]$ Proof Well known but anyway.Let $R=QP+S$ where $\mathrm{deg}(S)<\mathrm{deg}(Q)$.Now $\frac{S}{Q}$ is an integer for infinitely many numbers but $\lim_{x\rightarrow \infty}\frac{S(x)}{Q(x)}=0$ a clear clear contradiction as we're dealing with sequence of positive integers. Let $\tfrac{x^{n+1}-1}{x-1}=P(x)$ and let $\sum_{i=0}^{n!} x^{i!}=Q(x)$ $\implies$ $P\mid Q$ and hence all roots of $P$ are roots of $Q$ as well.Let $\omega$ be the $n+1$-nth root of unity by roots of unity filter (or just bunching terms) $\frac{\sum_{i=1}^{n+1}Q(\omega^i)}{n+1}=1=\text{The number of coeiffcient which degs are divisible by n+1}$ as the only non-zero term in the denominator is $Q(1)$ however from the second equality none of the $n!,(n-1)!,...1!$ is divisible by n+1 and hence n+1 is a prime. Let $\omega$ be the $p$ -th root of unity where $n+1:=p$.Now clearly again $Q(w)=0$ but as the minimal poly of $\omega$ is $x^{p-1}+x^{p-2}+...+1$ this implies that $\{n!,(n-1)!,(n-2)!,..1!,0\}$ for a complete residue system modulo $p$.However we have that $n!\equiv_p -1$ and so $(n-1)!\equiv_p 1$ but also $1!\equiv_p$ a contradiction.Hence $n$ is either one or two which by checking both work and are the only one that do.$\blacksquare$