Let $ a>1$ be a positive integer. Prove that every non-zero positive integer $ N$ has a multiple in the sequence $ (a_n)_{n\ge1}$, $ a_n=\left\lfloor\frac{a^n}n\right\rfloor$.
Problem
Source: 1st Romanian Master in Mathematics (RMIM) 2008, Bucharest, Problem 3
Tags: floor function, modular arithmetic, function, number theory, number theory proposed
11.02.2008 12:31
Strange problem. Let $ N=N_1N_2$, where $ N_2$ and $ a$ are coprime, and $ N_1$ divides $ a^C$ for suitable positive integer $ C$. Without loss of generality, $ CN_1$ divides $ a^{C}$ (we may take $ C$ being large power of $ a$). Take large prime $ p$ such that $ p-1$ is divisible by $ \varphi(n)$. The existence of such $ p$ is well-known elementary case of the Dirichlet theorem, which may be obtained using the cyclotomic polynomials. Then take $ n=pC$. Then by Fermat's little theorem we have $ [a^{Cp}/(Cp)]=(a^{Cp}-a^C)/(Cp)$, which is divisible by $ N=N_1N_2$.
19.03.2011 12:02
We can solve this problem without the Dirichlet theorem. There are positive integers $m$ and $M$ such that $GCD(m,M)=1, N\mid a^{m}M$. We consider $M>1$(it is obvious when $M=1$) Let $R$ is an integer such that $M^{R}>a^{m+\varphi(M)}$ and $a^{R} mod \varphi(M), a^{R+1} mod \varphi(M), a^{R+2} mod \varphi(M), ...$ is a periodical sequence(the period is not more than $\varphi(M)$). Then there exists an integer $0\le i\le\varphi(M)$ and $a^{a^{R}M^{R}-m-i}\equiv a^{R}\pmod{\varphi(M)}$. Let $k=a^{R}M^{R}-m-i$ and $n=a^{k}M^{R}$, then $ \varphi(M^{R+1})=M^{R}\varphi(M)\mid n-k-m-i\\ \Rightarrow a^{n-k-m-i}\equiv 1\pmod{M^{R+1}}\\ \Rightarrow a^{n-k}\equiv a^{m+i}\pmod{a^{m}M^{R+1}}\\ \Rightarrow \lfloor\dfrac{a^{n-k}}{M^{R}}\rfloor=\lfloor\dfrac{a^{n}}{n}\rfloor\\ =\lfloor\dfrac{Ia^{m}M^{R+1}+a^{m+i}}{M^{R}}\rfloor (I\in\mathbb{Z})\\ =Ia^{m}M+\lfloor\dfrac{a^{m+i}}{M^{R}}\rfloor=Ia^{m}M ( a^{m+i}\le a^{m+\varphi(M)}<M^{R})\\ \Rightarrow N\mid \lfloor\dfrac{a^{n}}{n}\rfloor\\ $
21.02.2013 22:26
This solution was found in collaboration with proglote. it is quite similar to Fedor Petrov's solution actually. Write $N = bc$ where $\gcd(c,a) = \gcd(b,c) = 1$. Let $b|a^k$ and $k$ clearly exists since $b$'s prime factors are purely those of $a$ as well. Then consider $n = a^kp$ for a prime $p \equiv 1 \pmod{\text{ord}_c(a)}$ and $p > \max(c,a^k - k)$ which exists by Dirichlet. It is easy to see that: \[\frac{a^{a^kp}}{a^kp} = \frac{a^{a^kp-k}}{p}\] Then remark that $a^{a^kp-k} \equiv a^{a^k-k} \pmod{p}$, so it follows \[a_{a^kp} = \frac{a^{a^kp - k} - a^{a^k-k}}{p}\] It is clear that $a^{a^k(p-1)}-1$ divides the numerator. It follows that as $c|(a^{a^k(p-1)}-1)$ due to the order condition and $\gcd(c,p) = 1$ due to $p > c$ that $c$ divides $a_{a^kp}$. It is also clear that $b$ must divide $a_{a^kp}$ as $a^{a^k-k}$ divides the numerator. Thus we are done as we have shown an arbitrary $N$ divides some term of the sequence.
30.01.2015 06:52
I solved it pretty ugly, no Dirichlet. Sorry I used different values. I want $k | floor(a^r/r)$ Instead of $r$ I used $ra^x$, and then I define $P$ very big and then $Q$ such that $ord_Q a=P$ and then $r$ such that $ord_r a= Q$ using two Zsigmondys. Then I can control $x$ in mod $d=ord_{k_1} a$ (where $k_1$ is biggest divisor of $k$ coprime to $a$), mod $ORD_d a$ (where $ORD$ is like the $ord$ function but without caring about $a$ and the modulus coprime), mod $P$ and mod $Q$ and use Chinese Theorem to finish, choosing $a^{ra^x-x} \equiv a^{c+i}$ (mod $kr$), where $c$ is such that $g | a^c$ ($g=k/k_1$) and $i<d$). $i$ is useful since $ORD_da$ and $d$ aren't necessarily coprime.
02.09.2015 13:57
Probably i am mistaken or this is on the easier end of RMM. Indeed let $p$ be a prime such that $p>a$ and $p$ is congruent to 1 modulo $\phi(N)$.(Clearly by the properties of cyclotomic polynomials infinitely many such $p$ exist or just use Weak Dirichlet's theorem) Now clearly $N$ divides $a_p$
12.04.2017 08:02
08.02.2019 09:17
I'll just post this cuz it's different from the above solutions. (Actually, #6 and #7 are really nice, but proving that there are infinitely many primes in the $nk+1$ takes a lot of time.)
. We'll prove that $n=b_m-1$ works for sufficiently large $m>2$. One can easily check that $$a_n=\left\lfloor\frac{a^n}n\right\rfloor=\left\lfloor\frac{a^{a^{b_{m-1}}-1}}{a^{a^{b_{m-2}}}-1}\right\rfloor=\frac{a^{a^{b_{m-1}}-1}-a^{a^{b_{m-2}}-1}}{a^{a^{b_{m-2}}}-1}=a^{b_{m-1}-1}\cdot\frac{a^{b_m-b_{m-1}}-1}{a^{b_{m-1}}-1}$$Now let $N=N_1N_2$, where $N_2$ is the largest divisor of $N_2$ such that $(a,N_2)=1$. We'll choose $m$ large enough so that $N_1|a^{b_{m-1}-1}$. Observe that for each $p|N_2$, the sequence $v_p(a^{b_m}-1)$ is bounded, so let $x_p$ be the upper bound. Using the well-known property of power-towers, find some $M$ such that $$m>M\Longrightarrow \phi(N_2\cdot\prod_{p|N_2}p^{x_p})|{b_m-b_{m-1}}$$, and we're done.
20.08.2020 15:05
Same as above solutions, posting for storage. Solution. Take a prime $p$, such that $p>a$ (1) and $p=k.\phi{N}$ (*) and $(p,N)=1$ (**)(existence is guaranteed by Dirichlet`s theorem). By FLT, $a^p-a$ is divisible by $p$ (2).From (1) and (2), we have that $a_p=\lfloor\frac{a^p}{p}\rfloor=\frac {a^p-a}{p}$. Using (*), (**) and Euler`s theorem, we immediately see that $a_p$ is divisible by $N$, which is what we need. $\blacksquare $