Let (a,b)=1 and T is minimal period b mod a ($ a|b^T-1, a|b^k-1\Longrightarrow T|k$). Then (T,a)=1 and define k, suth that $ kT=1\mod a$. It give for n=kT: $ a|b^n-n$. It may be when $ (a,b)\not =1$. Let (a,b)=c and $ a=ca_1,b=cb_1, (a_1,b_1)=1$. Then $ a|b^n-n$ only if $ c|n$. If $ (a_1,b)=1$ and $ T$ is period $ b$ mod $ a_1$, $ kcT=1\mod a_1$ then for $ n=kcT$ we get $ a|b^n-n$. By concider $ (a_1,c)=d,a_1=da_2$, we get, that exist n, suth that $ a|b^n-n$ for any a,b.

Rust wrote: Let (a,b)=1 and T is minimal period b mod a ($ a|b^T - 1, a|b^k - 1\Longrightarrow T|k$). Then (T,a)=1 It is not true. For example $ a=p^2$ and $ b$ is a primitive root mod a. Then $ T=p(p-1)$ This problem can be proof by Chinese remainder . Consider the $ n=p^a$

Yes. If $ b=p_1^{k_1}..p_m^{k_m}b_1,a=p_1^l_1..p_m^{l_m}a_1, (a_1,b_1)=1= (p_i,a_1)=(p_i,b_1)$, then from $ a|b^n-n$ we get $ n=n{}_0n{}_1, n_0=p_1^{l_1}...p_m^{l_m}$ and $ a|b^n-n$ if and only if $ a_1|b_2^{n_1}-n{}_0n{}_1$ were $ b_2=b^{n_0}$. Let $ a_2=rad(a_1)$. Then exist minimal period $ T$, suth that $ a_2|b_2^T-1$. Let $ k$ defined by $ kn_0T=1\mod a_2$ , ($ (T,a_2)=1$). It give solution $ a_2|b_2^{n_1}-n{}_0n{}_1$ ($ n_1=kT$). But case, when $ \frac{a_1}{a_2}$ had many prime divisors is difficult. Because chinese theorem does not work for full periods $ b^n-n$ and $ a=p_1^2p_2^2$ may be $ (T_1,T_2)\not =1$.

I thinks i have a solution! we will show that "there is infty n such that $ a|b^n-n,\forall a>1$" +) a=2, it's trivial +) Suppose it's true for a. we have $ \exists k,a_1: a|b^ka_1,gcd(a_1,b)=1$. Because $ \varphi(a_1)<a_1\leq a$ so there is infty n>k such that $ \varphi(a_1)|b^n-n$ $ \Rightarrow a_1|b^{b^n-n}-1$ $ \Rightarrow b^na_1|b^{b^n}-b^n$ $ \Rightarrow a|b^{b^n}-b^n$ with infty n. The proof is complete! Sorry if the text have some error

Let $ a_2 = rad(a_1)$. what is rad(a1)?

To type up langtuthanhdong's proof in a polished form: Let us proceed by induction. The base case $ a=2$ is trivial. Now, suppose that for all $ k<a$, there exists $ n$ such that $ b^n \equiv n \pmod{a}$. Let $ b=gb', a=ga'$, where $ (b',a')=1$. Then, $ \varphi(a')<a'<a$, so there exists $ n$ such that \[ \varphi(a')| b^n-n \] So \[ a' | b^{b^n-n}-1 \] So \[ b^na' | b^{b^n}-b^n \] But $ a | b^na'$, so \[ a | b^{b^n}-b^n \] And the induction is complete.

Phelpedo wrote: So \[ a' | b^{b^n - n} - 1 \] What if $ a=8$, $ b=4$? The proof seems to fail for $ (a',g)\neq1$

N.T.TUAN wrote: Determine whether or not there exist positive integers $ a$ and $ b$ such that $ a$ does not divide $ b^n - n$ for all positive integers $ n$. Well it just says to determine, so couldnt we just say "let a=5, b=3, and n=2 QED" and hope for at least partial credit?

We can say more: "Let $ a,c,d$ positive integer and $ b \in \{-1,1\}$ fixed, then there exist infinitely many positive integer $ x$ such that $ d \mid a^x+bx+c$". Have a look at here

I didn't see a confirmed solution here, so maybe the following will work: Answer is no, so we can always find such n with a to divide $ b^n-n$. We can first consider the case of modulo p. We have that $ b^n$ has cycle length at most p-1 (and which divides p-1); on the other hand, $ n$ just has cycle length p, hitting all the values. Thus, we can say that there are $ p-1$ values $ j$ in modulo $ p(p-1)$ such that $ b^j \equiv j \pmod{p(p-1)}$, all of these values $ j$ being different modulo p-1 (so there is a valid j for every modulo p-1 value). Now I claim that for any $ m>1$, we have p-1 values $ x$ in modulo $ p^{m-1}(p-1)$ such that $ b^x \equiv x \pmod{p^{m}}$, and such that the p-1 values are distinct mod p-1. To do this, we show that for any value $ x$ such that $ b^x \equiv x\pmod{p^{m-1}}$, we can find $ y\equiv x\pmod{p-1}$ with $ b^y\equiv y \pmod{p^{m}}$. We take $ y = s(p^{m}-p^{m-1}) + x$ (for some $ s$) and so $ b^{y} = b^{s(p^{m}-p^{m-1})+x} \equiv b^x \equiv x + s(p^{m}-p^{m-1}) \equiv y\pmod{p^m}$ for appropriately chosen $ s$. Thus, our claim is proven. Now, we can construct a number $ n$ with $ a|b^n-n$. Let $ a=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ such that they are ordered $ p_1<p_2 < \cdots <p_k$. Clearly we can construct $ n$ so that $ p_1^{e_1} | b^n - n$. Now, suppose we can construct one for some number of primes $ p_1^{e_1}$ through $ p_i^{e_i}$ dividing $ b^n-n$. This will hold for $ n$ restricted within a congruence modulo $ \phi (p_1^{e_1} \cdots p_i^{e_i})$. For $ p_{i+1}^{e_{i+1}}$ to divide $ b^n-n$, we will need to have $ n \equiv h\pmod{p_{i+1}^{e_{i+1}-1}(p-1)}$ for some $ h$. However, we can choose the value of $ h$ in modulo $ p_{i+1}-1$ by the claim from before, and we have that $ p_{i+1}$ is larger than all the prime factors of $ \phi (p_1^{e_1} \cdots p_i^{e_i})$. Thus, imposing this congruence of $ n\equiv h\pmod{p_{i+1}^{e_{i+1}-1}(p-1)}$ will have solution. Thus, we can construct n, so we are done.

Suppose, by way of contradiction, that there exist positive integers $a, b$ such that $a \nmid b^n - n$ for all $n \in \mathbb{N}.$ Then for a fixed $b$, let us examine the smallest positive integer $a$ such that $a \nmid b^n - n$ for all $n \in \mathbb{N}.$ Notice that trivially $a \ne 1.$ Now, consider the least exponent $d \in \mathbb{N}$ such that $b^{i + d} \equiv b^i \pmod{a}$ for all $i \in \mathbb{N}$, i.e. $d$ is the period of the sequence $b, b^2, b^3, \cdots \pmod{a}.$ Note that if $\gcd(a, b) = 1$, then all terms of this sequence are relatively prime to $a \implies d \le \phi(a) < a.$ Otherwise, if $a$ and $b$ share a common factor, then no term of this sequence is equal to $1.$ Therefore, there are at most $a - 1$ possible values for terms of this sequence, and it follows that $d < a.$ Now, since $d < a$, by the minimality of $a$, there must exist some $k \in \mathbb{N}$ such that $d \mid b^k - k.$ Hence, we can write $b^k = k + cd$ for some $c\in \mathbb{N}_0.$ Then let us take $n = b^k.$ By the definition of $d$, it follows that \[b^n - n = b^{b^k} - b^k = b^{k + cd } - b^k \equiv b^k - b^k \equiv 0 \pmod{a}.\] Hence, $a \mid b^n - n$, a contradiction. $\square$

Cases $a=1,2$ are trivial. Let $a$ be the least such positive integer. Then any prime dividing $a$ also satisfies this so we get a contradiction to the minimality of $a$ unless $a$ is a prime. Now let $p$ be a prime such that $p$ divides $a$. Put $n$ = $((1-b)+kp)(p-1)+1$. We get that $p$ divides $b^n -n$. Done.(as indeed by minimality $a$ =$p$) Its wrong dont consider this.

anantmudgal09 wrote: Cases $a=1,2$ are trivial. Let $a$ be the least such positive integer. Then any prime dividing $a$ also satisfies this so we get a contradiction to the minimality of $a$ unless $a$ is a prime. Now let $p$ be a prime such that $p$ divides $a$. Put $n$ = $((1-b)+kp)(p-1)+1$. We get that $p$ divides $b^n -n$. Done.(as indeed by minimality $a$ =$p$) This does not seem true to me! Dukejukem wrote: Now, consider the least exponent $d \in \mathbb{N}$ such that $b^{i + d} \equiv b^i \pmod{a}$ for all $i \in \mathbb{N}$. Because $b\left(b^{\phi(a)} - 1\right)$ is divisible by $a$, we have that \[b^i\left(b^{\phi(a)} - 1\right) \equiv 0 \pmod{a} \implies b^{i + \phi(a)} \equiv b^i \pmod{a}.\] If $p$ is a prime dividing both $a$ and $b$, and $v_p(b) < v_p(a)$, then this is not true for $i = 1$.

Oh yes i made some mistake (must be my lack of sleep) i will edit the previous post and will try it over again. Thanks a lot.

saturzo wrote: Dukejukem wrote: Now, consider the least exponent $d \in \mathbb{N}$ such that $b^{i + d} \equiv b^i \pmod{a}$ for all $i \in \mathbb{N}$. Because $b\left(b^{\phi(a)} - 1\right)$ is divisible by $a$, we have that \[b^i\left(b^{\phi(a)} - 1\right) \equiv 0 \pmod{a} \implies b^{i + \phi(a)} \equiv b^i \pmod{a}.\] If $p$ is a prime dividing both $a$ and $b$, and $v_p(b) < v_p(a)$, then this is not true for $i = 1$. Ah, thanks for the catch. I'll edit the proof accordingly.

I don't see this here? By a trivial extension of 1991 USAMO #3, the sequence $b, b^b, b^{b^b}, \cdots$, is eventually constant modulo $a$. Then, just take a sufficiently large power tower in $b$ for $n$, and it works trivially.

Dukejukem wrote: Now, consider the least exponent $d \in \mathbb{N}$ such that $b^{i + d} \equiv b^i \pmod{a}$ for all $i \in \mathbb{N}$, i.e. $d$ is the period of the sequence $b, b^2, b^3, \cdots \pmod{a}.$ I would like to see the proof of this periodicity when $(a,b)\neq 1$. Certainly, there exist $i,d\in Z_+$ as marked above. And from $b^d$ sequence will be periodic. But will he be periodic before $b^d$? If so, then how do you prove it?

Induction . Here's my solution (Hopefully correct): We claim that for each $(a,b),$ there exists some $n$ such that $a \mid b^n-n$. Consider the infinite sequence of positive integers defined as $b_1=b$ and $b_{k+1}=b^{b_k}$. Then the following Lemma is true:- LEMMA (USAMO 1991 P3) The sequence $<b_k>_{k \geq 1}$ eventually becomes constant modulo $a$. Proof of Lemma We use strong induction on $a$. For $a=1,2$ the result is obvious. Suppose our claim is true for $1,2, \dots ,a-1$. Consider the case when $\gcd(a,b)=d>1$. Choose some prime divisor $p$ of $d$. Note that, for sufficiently large $j$, $p^{\nu_p(a)} \mid b_j$. So we can effectively ignore $d$, and assume that $\gcd(a,b)=1$. Then it is well known that $$b_{k+1}=b^{b_k} \equiv b^{b_k \pmod{\phi(a)}} \pmod{a}$$But, by the induction hypothesis, for sufficiently large $k$, the sequence $<b_k>_{k \geq 1}$ eventually becomes constant modulo $\phi(a)$, giving the desired result. $\Box$ Return to the problem at hand. Then choosing $n=b_k$, for sufficiently large $k$ concludes our solution. Hence, done. $\blacksquare$ REMARK: Without knowing the Lemma, the problem can be difficult. Unfortunately, this happened with me, as I wasn't aware of it. Here's how I thought of it - It's quite intuitive to think that the answer is not affirmatory. The main difficulty lies in finding the desired $n$. On looking at the problem, one can see that $b^n$ and $n$ are not closely related, unless $n$ is a power of $b$. Then, trying some small cases, and to make things even more symmetric, I thought of introducing towers of $b$. Apparently they worked .

We claim that given any positive integers $a$ and $b$, there always exists a positive integer $n$ such that $a\mid b^n-n$. Note that replacing $a$ with any multiple of $a$ makes the problem strictly harder, so WLOG, we may assume that the prime factorization of $a$ is of the form $p_1^r\cdots p_k^r$ where $2=p_1<p_2<\cdots<p_k$ are all of the primes from $2$ to $p_k$. This won't actually affect the content of the proof, but will make the argument slightly easier to make. Let $M_i$ be $p_1\cdots p_i$. We claim that for each $1\le i\le k$, there exists integers $n_i$ and $N_i$, the latter of which is a multiple of $N_i$ with no new prime factors, such that $n\equiv n_i\pmod{N_i}$ implies $M_i\mid b^n-n$. We proceed by induction on $i$. The base case of $i=1$ is easy, since we may take $n_1=b$ and $N_1=p_1=2$. Now suppose that the statement is true for some $i$, and we want to show it for $i+1$. Note that $p_{i+1}-1$ has all prime factors from $p_1,\ldots,p_i$. Thus, by CRT, there is a solution $n_{i+1}$ to the system of congruences \begin{align*} n_{i+1} &\equiv n_i\pmod{N_i} \\ n_{i+1} &\equiv n_i\pmod{p_{i+1}-1} \\ n_{i+1} &\equiv b^{n_i}\pmod{p_{i+1}}, \end{align*}since $p_{i+1}$ is relatively prime to both $p_{i+1}-1$ and $N_i$. Let $N_{i+1}=\mathrm{lcm}(M_i,p_{i+1}-1,p_{i+1})$ and as said above, $n_{i+1}$ is a solution to the given system of congruences. If $n\equiv n_{i+1}\pmod{N_{i+1}}$, then $M_i\mid b^n-n$ by the first congruence and the induction hypothesis. Furthermore, by the last two, we see that $b^n\equiv b^{n_i}\pmod{p_{i+1}}$ and $n\equiv b^{n_i}\pmod{p_{i+1}}$, so $p_{i+1}\mid b^n-n$, as desired. Thus, by induction, there is some integer $L_1$ (which is just $N_k$) with prime factors only from $p_1,\ldots,p_k$ and some other integer $\ell_1$ (which is just $n_k$) such that \[n\equiv \ell_1\pmod{L_1}\implies p_1\cdots p_k\mid b^n-n.\]We claim that for all $1\le j\le r$, there exist integers $L_j$ (with all prime factors from $p_1,\ldots,p_k$, each at least $j$ times, and also divisible by $p_i-1$ for all $1\le i\le k$) and $\ell_j$ such that \[n\equiv\ell_j\pmod{L_j}\implies p_1^j\cdots p_k^j\mid b^n-n.\]The base case was established above, so like before, we suppose the result is true for $j$, and we're trying to show it for $j+1$. Let $\ell_{j+1}$ be the solution to all the systems of congruences \begin{align*} \ell_{j+1} &\equiv \ell_j\pmod{L_j} \\ \ell_{j+1} &\equiv \ell_j\pmod{p_i^j(p_i-1)} \\ \ell_{j+1} &\equiv b^{\ell_j}\pmod{p_i^{j+1}}, \end{align*}where $i$ ranges over all integers from $1$ to $k$ inclusive. Note that this only works because the third congruence and the first two conflict over a modulus that is a factor of $L_j$ since $L_j$ has at least $j$ factors of $p_i$ and is divisible by $p_i-1$, and $b^{\ell_j}\equiv\ell_j\pmod{L_j}$. Letting $L_{j+1}$ be the lcm of $L_j$ and all the $p_i^{j+1}$s (the $p_i-1$ if a factor of $L_j$ already), we see that $n\equiv\ell_{j+1}\pmod{L_j}$ means that \[b^n-n\equiv b^{\ell_j}-b^{\ell_j}\pmod{p_i^{j+1}},\]so $p_1^{j+1}\cdots p_k^{j+1}\mid b^n-n$, thus completing the induction. Therefore, there are integers $y$ (which is $\ell_r$) and $Y$ (which is $L_r$) such that \[n\equiv y\pmod{y}\implies a\mid b^n-n,\]so we're done.

There is always an integer $n$ that makes $b^n - n \equiv 0 \pmod{a}$ for given $a$ and $b$. Let us induct on $a$. For small $a$, such as 1, and 2, the claim holds true. For $a \geq 3$, assume that for some $b$ for no such $n$ $b^{n} - n \equiv 0 \pmod{a}$. Then, for no $n= b^k$, $b^{b^k} \equiv b^k \pmod{a}$. But this cannot be true by induction, as for some $k$, $b^{k} \equiv k \pmod{\phi(b)}$.

The answer is no; we claim that for all positive integers $a,b,$ there is some $n$ such that $a\mid b^n-n.$ To prove this, we will fix $b$ and induct on $a,$ the base case being clear. Suppose the claim is true for $a=2,3,\dots,k.$ If $\gcd(b,k+1)=1,$ then let $n=b^m,$ where $$b^{m}\equiv m\pmod{\varphi(k+1)}.$$(The inductive hypothesis guarantees that a solution exists) By Euler's Theorem, $b^n\equiv n\pmod{k+1}.$ If $\gcd(b,k+1)>1,$ then let $$d=\prod_{\text{p is prime, }p\mid b}p^{\nu_{p}(k+1)}.$$Now let $n$ be a solution to the congruence $$b^{n}\equiv n\pmod{(k+1)/d}.$$Since $\gcd(d,(k+1)/d)=1,$ we have $b^n\equiv n\pmod{k+1},$ as desired.

The answer is no. Since $\varphi(n)<n$ for all $n>1$, consider $k \geq 0$ such that $\varphi^k(a)=1$, which must exist. Now let $n={^{k}b}$ (denoting tetration), so $b^n={^{k+1}b}$. Then by Euler Totient $${^{k+1}b}\equiv {^{k}b} \pmod{a} \impliedby {^{k}b}\equiv {^{k-1}b} \pmod{\varphi(a)} \impliedby \cdots \impliedby {^{1}b}=b\equiv 1={^{0}b} \pmod{\varphi^k(a)},$$which is true as clearly $1 \mid b-1$.

The answer is no. We claim that $\underbrace{b^{b^{\cdots^b}}}_{n}$ is eventually constant $\pmod a$. We will prove this by induction on $a$. Indeed, the basis of $a=1$ is trivial. Now, assume the result holds for every positive integer less than $a$. We let $f(n)=\underbrace{b^{b^{\cdots^b}}}_{n}$. Let the period of $b,b^2,b^3, \ldots$ mod $a$ be $d$ which is strictly less than $a$. By our hypothesis, $f(k)$ is eventually constant mod $d$ and thus, $b^{f(m)}=f(m+1)$ is eventually constant mod $a$. So, letting $n=f(N)$ for sufficiently large $N$ yields $b^{f(N)}-f(N) = f(N+1)-f(N)$ which is divisible by $a$.

This is quite tricky for TST4; the obvious solution of ``solve the problem for $a = p^k$ and then generalize" doesn't work very well, and you need to tailor it. The answer is no; fix $a = p_1^{k_1} p_2^{k_2} \cdots p_\ell^{k_\ell}$. We prove that no such $b$ exists for $a =(p_1p_2 \cdots p_\ell)^k$ for all positive integers $k$ by induction, which will imply the result. Now instead of looking at the primes separately, we look at them together! The base case $k=0$ is vacuous. For the inductive step, suppose we have an $n_0$ such that $$b^{n_0} - n_0 = c(p_1p_2 \cdots p_\ell)^k$$for some constant $c$. Then, observe that $$b^{n_0+r\prod_{i=1}^\ell p_i^k(p_i-1)} - n_0 - ip_1^k p_2^k \cdots p_\ell^k(p_1-1)(p_2-1) \cdots (p_\ell - 1) \equiv p_i^k\left(\prod_{j \neq i} p_i^k \right)(c-r(p_1-1)(p_2-1)\cdots (p_\ell - 1)) \pmod {p_i^{k+1}}$$because the exponent term is congruent to $b^{n_0}$ by Euler totient. On the other hand, by picking a suitable $r$ modulo $p_i$, we can guarantee that $$p_i \mid c - r(p_1-1)(p_2-1) \cdots (p_\ell - 1)$$and thus $p_i^{k+1}$ divides the original expression. We may collate this across all $p_i$ by Chinese Remainder Theorem to complete the inductive step.

The answer is no. We proceed by induction, suppose that for all $k<a$ it exists an $n$ such that $a\mid b^n-n$, where are going to prove the statement for $a$, Let $\gcd(a,b)=k$, as $\phi(\frac{a}{k})<a$ then \begin{align*} \phi(\frac{a}{k}) &\mid b^n-n \\ \frac{a}{k} &\mid b^{\left(b^n-n\right)}-1 \\ \frac{a}{k}\cdot b^n &\mid b^{b^n}-b^n\\ a &\mid b^{b^n}-b^n \end{align*}We are done Note that the problem it´s trivial after seeing 1991 USAMO #3

We will prove that for every a,b there exist inifinitely many natural numbers n, such that a divides b^n-n. Our proof will be by strong induction on a. base case, a=1: 1 divides b^n-n for each natural n, so this is solved Suppose the statement holds for 1,2,...,a-1. Let a = c * d, where gcd(d,c) = gcd(d,b) = 1 (meaning, all of the primes in b and in a are in c, all of the other ones are in d). Take phi(d) < d <= a, by induction we have infinitiely many numbers y for which phi(d) divides b^y-y. For each of these numbers y, d divides b^(b^y-y) - 1 by eulers theorem, so it also divides b^y*(b^(b^y-y) -1) = b^(b^y)-b^y. So now we have infinitely many numbers y for which this d divides b^(b^y)-b^y, and also all of the prime factors of c are among the prime factors of b. Well now we can easily only pick those y for which c divides b^y (they just need to be large enough). For all of these a = c*d will divide b^(b^y)-b^y, and there are infinitely many of them so we are done