### baowilliam's blog

By baowilliam, history, 14 months ago,

with $(0\leq n\leq 2^{31}-1)$ caculate: $(2^{2^{n}} + 1)$ mod k $(1\leq k\leq 10^{6})$ i'm doing an exercise on mods for large numbers, i don't know if there is a more efficient solution than using binary exponentiation? Hope to help you, thanks (sorry for my bad english!!!!)

• +26

| Write comment?
 » 14 months ago, # |   +5 Assuming the case when $k$ is a prime number.Let, ${ans = (2^{2^n} + 1)}$ mod $k$let's modify a little bit${2^{2^n}}$ mod ${k = (ans + k - 1)}$ mod $k$ ${ = x}$Using Fermat Little Theorem, let ${p = (2 ^ n)}$ mod $(k - 1)$so, ${x = (2 ^ p)}$ mod $k$.so you may easily calculate $p$ first then calculate $x$ then can form the $ans$ easily :)
•  » » 14 months ago, # ^ |   +19 thank you!!!, btw how about the case when k is not co-prime with 2 :(
 » 14 months ago, # | ← Rev. 7 →   0 Deleted.
 » 14 months ago, # | ← Rev. 6 →   +2 You can use the extension of Fermat's little theorem, the so-called Euler's Theorem. According to the theorem, the following is true. $n^{\phi(m)} \equiv 1\pmod m$Therefore the following is also true: $n^k\equiv n^{k\bmod\phi(m)}\pmod m$These problems, in CP and MO, are called Power Towers. They usually ask for a very big power modulo a composite number like these. $a_0^{a_1^{a_2^{a_3^{a_4^{{\text{(omitted some powers)}}^{a_n}}}}}} \bmod m$(btw how do I use antidiagonal dots on LaTeX? this long text looks ugly as heck)
•  » » 14 months ago, # ^ |   +11 but we just can use fermat's little theorem if and only if (n and m) are co-prime, <=> 2 and k are co-prime, and I really don't know the case when 2 and k aren't co-prime :(, can you explain a little bit?
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +12 Oops, I forgot to also explain this, the following is true regardless of whether the two are coprime or not. $x^{n}\equiv x^{\phi(m)+[n \bmod \phi(m)]} \mod m$UPD: LipArcanjo is correct, the exponent needs to exceed log2(m) for this
 » 14 months ago, # | ← Rev. 2 →   0 Edit: as of chromate00's reply/explanation, I've realized this solution is bad and ugly. One should refer to his messages for a better solution. Previous messageIf n <= 5, $2^n <= 32$, so you can compute the result in a long long with no special tricks. Now, for n >= 6...Let exp2 be the exponent of 2 in the prime decomposition of k. Let m be $k / 2^{exp2}$. We now have that 2 and m are coprime. Perfect!Now, we can use chromate00's neat technique as such:We know that $2^{2^{n}-exp2} \equiv 2^{(2^{n}-exp2) \ mod \ \phi(m)} \ (mod \ m)$.$(2^{n}-exp2) \ mod \ \phi(m)$ can easily be calculated (totient function computation, then binary exponentiation and basic modulo subtraction). Since the result to this mod is <= m, we can use binary exponentiation again to find $2^{(2^{n}-exp2) \ mod \ \phi(m)} \ (mod \ m)$, which is equal to $2^{2^{n}-exp2} \ (mod \ m)$.Let this result be x. We have that $2^{2^{n}-exp2} \ \equiv \ x \ (mod \ m)$. We can multiply this by $2^{exp2}$, thus getting: $2^{2^{n}} \ \equiv \ x * 2^{exp2} \ (mod \ k)$ (remember that m is $k / 2^{exp2}$). Finally, $2^{2^{n}}+1 \ \equiv \ x * 2^{exp2}+1 \ (mod \ k)$.Do a mod on $x * 2^{exp2}+1$ and that's your answer! Let me know if there is anything you don't understand.
 » 14 months ago, # |   +8 The statement:$n^e \ mod \ m = n^{\phi(m) + e \ mod \ \phi(m)} \ mod \ m$is true for all $n ,m,$ and $e \geq log_2(m)$. Source: https://nordic.icpc.io/ncpc2016/ncpc2016slides.pdf Problem E.So If $n$ is greater or equal then $log_2(k)$, you use the equation, if not, you can compute $2^n$.