Intereting Posts

Why are primitive roots of unity the only solution to these equations?
Gradient of a function restricted to a submanifold
Is arrow notation for vectors “not mathematically mature”?
Are these zeros equal to the imaginary parts of the Riemann zeta zeros?
Closed form for $\sum_{n=1}^\infty\frac{(-1)^n n^4 H_n}{2^n}$
Element of a set?
Show that $\left | \sin a – \sin b \right | \leq \left | a-b \right |$
Deriving volume of parallelepiped as a function of edge lengths and angles between the edges
Why do these two integrals use roots of reciprocal polynomials?
If $f\in\hbox{Hom}_{\mathbb{Z}}(\prod_{i=1}^{\infty }\mathbb{Z},\mathbb{Z})$ and $f\mid_{\bigoplus_{i=1}^{\infty } \mathbb{Z}}=0$ then $f=0$.
Solving $2^x \equiv x \pmod {11}$
Is $1847^{2013}+2$ really a prime?
For nonzeros $A,B,C\in M_n(\mathbb{R})$, $ABC=0$. Show $\operatorname{rank}(A)+\operatorname{rank}(B)+\operatorname{rank}(C)\le 2n$
How to prove that a bounded linear operator is compact?
How does the axiom schema of replacement work?

e.g., $n = 3$. Clearly, the powers of $2$ modulo $3$ alternate $2, 1$. The powers of $4$ modulo $3$ are all $1$s. So a power tower of $2$s modulo $3$ must get stuck on $1$. Of course this method is inefficient, as $n = 5$ already shows. Is there a formula, or at least a more efficient method?

p.s. I tried Mathematica’s `FixedPoint`

function but got very confused on the syntax, like whether to do `2, #`

or `#, 2`

.

- Prime Numbers And Perfect Squares
- Bezout's Theorem
- Last digits, numbers
- Congruence modulo p
- A question about numbers from Euclid's proof of infinitude of primes
- Why is 1 not a prime number?

- $\sum_{i=1}^n \frac{n}{\text{gcd}(i,n)}.$
- How to prove if this equation provides an integral solution divisible by $3$?
- How prove this $(p-1)!\left(1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}\right)\equiv 0\pmod{p^2}$
- For what $n$ is it true that $(1+\sum_{k=0}^{\infty}x^{2^k})^n+(\sum_{k=0}^{\infty}x^{2^k})^n\equiv1\mod2$
- Solving $13\alpha \equiv 1 \pmod{210}$
- Question about the totient function and congruence classes
- If $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \cdot\gcd(b, c)$
- Can Euclid's Division Algorithm and/or Fundamental Theorem of Arithmetic implies this property of prime numbers
- How to prove $ \prod_{d|n} d= n^{\frac{\tau (n)}{2}}$
- Foundational proof for Mersenne primes

Thinking about this as a fixed point is a bit misleading, since $k \mapsto 2^k$ is not a well defined function from $\mathbb{Z}/n \to \mathbb{Z}/n$. However, you are right that the sequence $2$, $2^2$, $2^{2^2}$, … is eventually constant modulo $n$ for any $n$.

**Proof by induction on $n$:** Let $n = 2^k s$ for $s$ odd. By the Chinese remainder theorem, it is enough to prove that the sequence is eventually constant modulo $2^k$ and modulo $s$. The claim modulo $2^k$ is obvious — the sequence is eventually zero. For $s$ odd, since $GCD(2,s) =1$, the value of $2^x$ modulo $s$ is determined by $x$ modulo $\phi(s)$. By induction, the sequence is eventually constant modulo $\phi(s)$, so it is also eventually constant modulo $s$ and we are done. $\square$.

Here is a straightforward Mathematica implementation.

```
oddPart[x_] := If[OddQ[x], x, oddPart[x/2]];
powerOfTwo[x_] := If[OddQ[x], 1, 2*powerOfTwo[x/2]];
eventualValue[1] = 0;
eventualValue[n_] :=
With[{s = oddPart[n], t = powerOfTwo[n]},
ChineseRemainder[{PowerMod[2, eventualValue[EulerPhi[s]], s] , 0}, {s, t}]];
```

The command `PowerMod[a,b,m]`

computes $a^b \bmod m$ in a way which is faster and more memory efficient than `Mod[a^b,m]`

. Other potential optimizations which I haven’t implemented would be to memoize `eventualValue`

, and to use bit shifting tricks to compute `oddPart`

and `powerOfTwo`

.

If $n$ is even, then there is no such value. For $n$ odd, you can use Carmichael’s Function (wich would be equivalent to Euler’s Totient for an odd $n$)

- Ways of coloring the $7\times1$ grid (with three colors)
- Generating functions and the Riemann Zeta Function
- Weights – Objects into bags puzzle
- $E \subset \mathbb R$ is an Interval $\iff E$ Is connected
- How to prove that the implicit function theorem implies the inverse function theorem?
- Proving “The sum of n consecutive cubes is equal to the square of the sum of the first n numbers.”
- Given a probability matrix, find probability that person at zero index can go to other rows
- Are infinitesimals dangerous?
- Prove that: $2^n < n!$ Using Induction
- Prime numbers of the form $(1\times11\times111\times1111\times…)-(1+11+111+1111+…)$
- Number of straight line segments determined by $n$ points in the plane is $\frac{n^2 – n}{2}$
- Limit of $\sqrt{x^2-6x+7}-x$ as x approaches negative infinity
- Is this an equivalent statement to the Fundamental Theorem of Algebra?
- How prove this $g(x)=\sup{\{f(x,y)|0\le y\le 1\}}$ is continuous on $$
- Express logic puzzles with proposition calculus notation