Intereting Posts

On order of elements of a infinite group
Expressing the determinant of a sum of two matrices?
When does $V/\operatorname{ker}(\phi)\simeq\phi(V)$ imply $V\simeq\operatorname{ker}(\phi)\oplus\phi(V)$?
Find the value of $\lim_{n\to \infty}\sum_{k=0}^n\frac{x^{2^k}}{1-x^{2^{k+1}}}$.
Prove (or disprove) the equivalence of AP, LUB, NIT and MCT
How to show that $\sqrt{1+\sqrt{2+\sqrt{3+\cdots\sqrt{2006}}}}<2$
Integrating $\int^{\infty}_0 e^{-x^2}\,dx$ using Feynman's parametrization trick
Prove that $F_n={n-1 \choose 0 }+{n-2 \choose 1 }+{n-3 \choose 2 }+\ldots$ where $F(n)$ is the $n$-th fibonacci number
Decoding and correcting $(1,0,0,1,0,0,1)$ Hamming$ (7,4)$ code
How to prove $2+2=4$ using axioms of real number system?
What could be better than base 10?
Why the need of Axiom of Countable Choice?
Attempting to find a specific similarity (equivalence) matrix
Find two elements that don't have a gcd in a subring of Gaussian integers
Ascending chain conditions on homogeneous ideals

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.

- which odd integers $n$ divides $3^{n}+1$?
- Prove that 10101…10101 is NOT a prime.
- Is $2^{1093}-2$ a multiple of $1093^2$?
- Integer $2 \times 2$ matrices such that $A^n = I$
- Prove that none of $\{11, 111, 1111,\dots \}$ is the perfect square of an integer
- Value of cyclotomic polynomial evaluated at 1

(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.)

- Direct proof that $(5/p)=1$ if $p\equiv 1\pmod{5}$.
- Show that $p$ is prime if the following limit property holds
- If $m^4+4^n$ is prime, then $m=n=1$ or $m$ is odd and $n$ even
- Dividing the linear congruence equations
- Given that $p$ is a prime and $p\mid a^n$, prove that $p^n\mid a^n$.
- Proof of Bezout's Lemma using Euclid's Algorithm backwards
- Any $p + 1$ consecutive integers contain at least two invertible elements modulo $p!!$ if $p$ is odd
- On the number divisors of a number
- Prove that if the equation $x^{2} \equiv a\pmod{pq}$ has any solutions, then it has four solutions.
- $15x\equiv 20 \pmod{88}$ Euclid's algorithm

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.)

- Number of distinct arrangements {$n_i$} $n_1<n_2<n_3<n_4<n_5$ such that $\sum n_i=20$
- if $A, B$ are open in $\mathbb R$ then so is $A+B.$
- Bayes Theorem confusion… (more complex)
- Smooth functions with compact support are dense in $L^1$
- Evaluation of $\int_{0}^{\frac{\pi}{2}}\left(\frac{1+\sin 3x}{1+2\sin x}\right)dx$ and $\int_{0}^{2} \left(\sqrt{1+x^3}+\sqrt{x^2+2x}\right)dx$
- Does the equality $1+2+3+… = -\frac{1}{12}$ lead to a contradiction?
- Banach-Space-Valued Analytic Functions
- How to $\int e^{-x^2} dx$
- Find the bearing angle between two points in a 2D space
- Is there a constructive proof of this characterization of $\ell^2$?
- Need help proving this integration
- Why are addition and multiplication commutative, but not exponentiation?
- Show that if $ab \equiv ac$ mod $n$ and $d=(a,n)$, then $b \equiv c$ mod $\frac{n}{d}$
- Integral involving Modified Bessel Function of the First Kind
- Solovay's Model and Choice