Modular Tetration

Key characterization

The sequence is scary-looking, but the only thing that matters is the multiplicative order of $a$ modulo $m$.

First, if $gcd(a,m)>1$, then every $b_n=a^{b_{n-1}}$ for $n \ge 1$ also shares a common prime factor with $m$. So $b_n$ can never be congruent to $1$ modulo $m$. Non-units are dead immediately.

Now assume $gcd(a,m)=1$. Let

$d = ord_m(a)$.

Then

$a^e \equiv 1 \pmod m$ iff $d \mid e$.

So for large $n$, we need

$b_n = a^{b_{n-1}} \equiv 1 \pmod m$,

which is equivalent to

$d \mid b_{n-1}$.

But $b_{n-1}$ is also a power of $a$. A number $d$ eventually divides powers of $a$ exactly when every prime divisor of $d$ already divides $a$. The exact exponents do not matter long-term, because the tower exponent gets huge. If a prime is present in $a$, its valuation in $a^{b_k}$ eventually becomes large enough. If a prime is missing from $a$, it never appears. Math is brutal like that.

So we have the core criterion:

A positive integer $a$ is $m$-tetrative iff $gcd(a,m)=1$ and every prime divisor of $ord_m(a)$ divides $a$.

The case $ord_m(a)=1$ is included automatically.

Turning the criterion into a density

Fix a unit residue $r$ modulo $m$, and let

$d = ord_m(r)$.

Every integer $a \equiv r \pmod m$ has the same order modulo $m$, namely $d$.

We need $a$ to be divisible by every prime in $rad(d)$.

If some prime $q \mid rad(d)$ also divides $m$, then this is impossible: $a \equiv r \pmod m$ is a unit, so $q \nmid a$. This residue contributes $0$.

Otherwise, all primes in $rad(d)$ are coprime to $m$. By CRT, among integers with $a \equiv r \pmod m$, the extra requirements $q \mid a$ for all $q \mid rad(d)$ cut the density by exactly $rad(d)$.

So residue $r$ contributes

$1/(m\,rad(d))$

if $gcd(rad(d),m)=1$, and contributes $0$ otherwise.

Therefore the full density is

$D = (1/m) * sum 1/rad(ord_m(r))$,

where the sum is over unit residues $r$, but residues whose order has a prime factor also dividing $m$ are skipped.

The group sum factorizes

Let $G = (Z/mZ)^*$ be the unit group. Its size is $phi(m)$.

For each prime $q \mid phi(m)$, let $G_q$ be the Sylow $q$-subgroup of $G$. Since $G$ is finite abelian,

$G = product_q G_q$,

and

$|G_q| = q^{e_q}$, where $e_q = v_q(phi(m))$.

For an element $r \in G$, the prime $q$ divides $ord_m(r)$ iff the $q$-component of $r$ is not the identity.

Now split primes $q \mid phi(m)$ into two types.

If $q \mid m$, then $q$ is forbidden: if the $q$-component is nonidentity, then $q \mid ord_m(r)$, so we would need $q \mid a$, impossible for a unit modulo $m$. Therefore the $q$-component must be identity. This gives factor $1$.

If $q \nmid m$, then this prime is allowed. In $G_q$:

• the identity component contributes weight $1$;
• each of the $q^{e_q}-1$ nonidentity components makes $q$ appear in $rad(ord)$, so it contributes weight $1/q$.

So this prime contributes the factor

$1 + (q^{e_q}-1)/q$.

Multiplying independent Sylow choices gives the whole sum. Thus the answer is

$D = (1/m) * product_{q | phi(m), q not | m} (1 + (q^{v_q(phi(m))}-1)/q)$.

That is the entire problem. The 3100 part is mostly noticing that the tower collapses into a Sylow-product counting problem, not doing any cursed tower simulation.

Computing it

We are given $m=xyz$, with $x,y,z \le 10^6$. So every prime factor of $m$ is at most $10^6$, and we can factor everything with a smallest-prime-factor sieve.

From the factorization

$m = product p^a$,

we factor

$phi(m) = product p^{a-1}(p-1)$.

So for each prime power $p^a$ in $m$:

• add $a-1$ to the exponent of $p$ in $phi(m)$;
• factor $p-1$ and add those primes too.

Finally compute the formula modulo $998244353$:

• multiply by $m^{-1}$;
• for every prime $q$ in $phi(m)$ that is not in $m$, multiply by $1+(q^e-1)/q$ modulo MOD.

All denominators are invertible modulo MOD here, since all relevant primes and input factors are less than MOD.