Intereting Posts

Given that $p$ is a prime and $p\mid a^n$, prove that $p^n\mid a^n$.
The convergence of a sequence with infinite products
Can $\pi$ be a root of a polynomial under special cases?
Is there a distributive law for ideals?
The set of rational numbers of the form p/p', where p and p' are prime, is dense in $[0, \infty)$
Riemann-Stieltjes integral of unbounded function
The least value of $b$ such that $2^{3^{\cdots^a}}\leq b^{(b-1)^{\cdots^2}}$
Derivation of Variance of Discrete Uniform Distribution over custom interval
Why is the topology of compactly supported smooth function in $\mathbb R^d$ not first countable?
Surprising Generalizations
Dimension of the total ring of fractions of a reduced ring.
Proving a real valued function is periodic, and sketching it using obtained information
Ellipse in polar coordinates
Why can/do we multiply all terms of a divisor with polynomial long division?
How do I show that the derivative of the path $\det(I + tA)$ at $t = 0$ is the trace of $A$?

A friend recently asked me if I could solve these three problems:

(a) Prove that the sequence $ 1^1, 2^2, 3^3, \dots \pmod{3}$ in other words $\{n^n \pmod{3} \}$ is periodic, and find the length of the period.

(b) Prove that the sequence $1, 2^2, 3^{3^3},\dots \pmod{4}$ i.e. $\{\ ^nn \pmod{4}\}$ is periodic and find the length of the period.

- Solve $3x^2-y^2=2$ for Integers
- Showing that $f_{2n+1}=f_{n+1}^2+f_n^2$.
- Factoring polynomials of the form $1+x+\cdots +x^{p-1}$ in finite field
- $(a^{n},b^{n})=(a,b)^{n}$ and $=^{n}$?
- Show that $17 \mid 15! -1$
- Find all integer solutions to $7595x + 1023y=124$

(c) Prove that the sequence $1, 2^2, 3^{3^3},\dots \pmod{5}$ i.e. $\{\ ^nn \pmod{5}\}$ is periodic and find the length of the period.

The first two were not terribly difficult (but might be useful exercises in Fermat’s little theorm), but the third one is causing me problems, since my methods are leading to rather a lot of

individual cases, and I would be interested to see if anyone here can find a neater way to solve it.

(In (c), I have evaluated the first 15 terms, and not found a period yet – unless I have made a mistake.)

- How to show that $\gcd(ab,n)=1$?
- Prove or disprove that $\exists a,b,c\in\mathbb{Z}_+\ \forall n\in\mathbb{Z}_+\ \exists k\in\mathbb{Z}_+\colon\ a^k+b^k+c^k = 0(\mathrm{mod}\ 2^n)$
- Wilson's Theorem - Why only for primes?
- prime divisor of $3n+2$ proof
- Deleting any digit yields a prime… is there a name for this?
- Why is reminder of $8^{30} / 7$ same as that of $1^{30} / 7$
- What is a negative number?
- Are all non-squares generators modulo some prime $p$?
- If : $\binom{p-1}{k} \equiv (-1)^k \pmod p$ for all $k$ then $p$ is a prime?
- Euler's totient and divisors count function relationship when $ = n$

We will need the following slight generalization of the totient theorem: $a^{k + \varphi(n)} \equiv a^k \bmod n$ for all $a$ provided that $k$ is at least as large as the largest exponent in the prime factorization of $n$.

It follows that

$$a^b \equiv a^{b \bmod 4} \bmod 5$$

provided that $b \ge 1$, and

$$b^c \equiv b^{c \bmod 2} \bmod 4$$

provided that $c \ge 2$ (where we need to take the remainder in $\{ 2, 3\}$). Finally,

$$c^d \equiv c \bmod 2$$

provided that $d \ge 1$. In summary,

$$a^{b^{c^d}} \equiv a^{b^c} \bmod 5$$

provided that $b \ge 1, c \ge 2, d \ge 1$. But this expression only depends on the value of $a \bmod 5, b \bmod 4, c \bmod 2$, so the sequence in question has eventual period dividing $20$, and computations of the first few terms suffices to show that the eventual period is an actual period. A similar argument works for $5$ replaced by any positive integer $m$ (but there is no guarantee that the eventual period is an actual period in this generality and I expect this to be false); we get that the eventual period divides $\text{lcm}(m, \varphi(m), \varphi(\varphi(m)), …)$. And of course we can replace $\varphi(m)$ by the Carmichael function for larger $m$ to get better bounds.

For $k\ge 1$ we have

$$\begin{align*}

{^{k+2}n}\bmod5&=(n\bmod5)^{^{k+1}n}\bmod5=(n\bmod5)^{^{k+1}n\bmod4}\bmod5\\

{^{k+1}n}\bmod4&=(n\bmod4)^{^kn}=\begin{cases}

0,&\text{if }n\bmod2=0\\

n\bmod4,&\text{otherwise}\;,

\end{cases}

\end{align*}$$

so

$${^{k+2}n}\bmod5=\begin{cases}

(n\bmod5)^0=1,&\text{if }n\bmod2=0\\

(n\bmod5)^{n\bmod4},&\text{otherwise}\;.

\end{cases}$$

In particular,

$${^nn}\bmod5=\begin{cases}

(n\bmod5)^0,&\text{if }n\bmod2=0\\

(n\bmod5)^{n\bmod4},&\text{otherwise}\;.

\end{cases}$$

for $n\ge3$, where $0^0\bmod5$ is understood to be $0$. Clearly the period starting at $n=3$ is a multiple of $20$; actual calculation shows that it is $20$, and that we cannot include the first two terms::

$$\begin{array}{r|c|c}

n:&&&&&&&&&1&2\\

{^nn}\bmod5:&&&&&&&&&1&4\\ \hline

n:&3&4&5&6&7&8&9&10&11&12\\

{^nn}\bmod5:&2&1&0&1&3&1&4&0&1&1\\ \hline

n:&13&14&15&16&17&18&19&20&21&22&\\

{^nn}\bmod5:&3&1&0&1&2&1&4&0&1&1

\end{array}$$

(**Added:** And no, I’d not seen that Qiaochu had already answered the question until after I posted.)

- Can every infinite set be divided into pairwise disjoint subsets of size $n\in\mathbb{N}$?
- Showing that $\lim\limits_{x \rightarrow 0} \frac{1}{x}$ does not exist.
- limit of quotient of two series
- Follow-up to $f(x)^2 = f(\sqrt2 x)$
- Proof that if $s_n \leq t_n$ for $n \geq N$, then $\liminf_{n \rightarrow \infty} s_n \leq \liminf_{n \rightarrow \infty} t_n$
- If $\alpha\leq \beta,\gamma\leq \delta$ then $\alpha+\gamma\leq \beta+\delta$
- Flaw or no flaw in MS Excel's RNG?
- $\lim_{x\to0} \frac{x-\sin x}{x-\tan x}$ without using L'Hopital
- Research in plane geometry or euclidean geometry
- How would I find a minimum weight spanning tree for W?
- $f\colon M\to N$ continuous iff $f(\overline{X})\subset\overline{f(X)}$
- Group structure from involutions, exercise devised by Richard Brauer.
- Relative interior commutes with cartesian product
- Topology such that function is continuous if and only if the restriction is.
- Prove that if $a$ and $b$ are odd, coprime numbers, then $\gcd(2^a +1, 2^b +1) = 3$