TobyBartels on Nostr: So we want to know whether ((123123×5↑↑10)%999999)%1001 = 0, where a↑↑n is ...

So we want to know whether ((123123×5↑↑10)%999999)%1001 = 0, where a↑↑n is tetration and a%b is remainder modulo b. By Euler's theorem, a^n%b = a^(n%φ(b))%b if gcd(a,b)=1. Less famously, a^n%(ab) = a^(n%φ(b))%(ab) if gcd(a,b)=1 and n%φ(b)>0. Since a↑↑(n+1)=a^a↑↑n, we can find a↑↑(n+1)%b recursively as a^(a↑↑n%φ(b))%b, and a↑↑(n+1)%(ab) as a^(a↑↑n%φ(b))%(ab), if the relevant conditions are met, starting with a↑↑0 = 1.

Since the totient φ(999999) is 466560, we could be in trouble, but 466560/5 is 93312, so we'll be fine. Applying the totient function 9 more times, there are no more multiples of 5, and we find that φ^9(93312) is 16, so I'll start there.

5↑↑0%16 = 1%16 = 1.
5↑↑1%32 = 5^(5↑↑0%16)%32 = 5^1%32 = 5.
5↑↑2%64 = 5^(5↑↑1%32)%64 = 5^5%64 = 53.
5↑↑3%128 = 5^(5↑↑2%64)%128 = 5^53%128 = 117.
5↑↑4%384 = 5^(5↑↑3%128)%384 = 5^117%384 = 245.
5↑↑5%1152 = 5^(5↑↑4%384)%1152 = 5^245%1152 = 245.
5↑↑6%3456 = 5^(5↑↑5%1152)%3456 = 5^245%3456 = 245.
5↑↑7%10368 = 5^(5↑↑6%3456)%10368 = 5^245%10368 = 3701.
5↑↑8%31104 = 5^(5↑↑7%10368)%31104 = 5^3701%31104 = 3701.
5↑↑9%466560 = 5^(5↑↑8%31104)%466560 = 5^3701%466560 = 34805.
5↑↑10%999999 = 5^(5↑↑9%466560)%99999 = 5^34805%465560 = 345467.
(123123×5↑↑10)%999999 = (123123×345467)%999999 = 975975.
975975 % 1001 = 0.

So Yes!