# If $p$ and $q$ are coprime positive integers s.t. $\frac{p}{q}=\sum_{k=0}^{100}\frac1{3^{2^k}+1}$, what is the smallest prime factor of $p$?

If the sum $$S=\frac14+\frac1{10}+\frac1{82}+\frac1{6562}+\cdots+\frac1{3^{2^{100}}+1}$$ is expressed in the form $$\frac pq,$$ where $$p,q\in\mathbb N$$ and $$\gcd(p, q) =1.$$ Then what is smallest prime factor of $$p$$ ?

We have: $$S=\sum_{k=0}^{100} \frac1{3^{2^k}+1}.$$ Please give me some hints to evaluate such kind of sums, in general.

Remark.

• Since $$4$$ divides the denominator of the zeroth term ($$\frac14$$) of $$S$$, but does not divide the denominator of any other term, we can see that $$2\nmid p$$.

• Note that each term of $$S$$ is $$\equiv 1\pmod{3}$$. Therefore, $$S\equiv 101\cdot 1\equiv 2\pmod{3}$$, so $$3\nmid p$$.

• Since $$5$$ divides the denominator of the first term ($$\frac1{10}$$) of $$S$$, but not the denominator of any other term, we conclude that $$5\nmid p$$.

• Perhaps, the only way is via bruteforcing. For example, observe that $3^{2^k}$ modulo $7$ for $k=0,1,2,\ldots$ are $$3,2,4,2,4,2,4,\ldots\,.$$ That is, $\dfrac{1}{3^{2^k}+1}$ modulo $7$ for $k=0,1,2,\ldots$ are $$2,5,3,5,3,5,3,\ldots\,.$$ That is, $S$ modulo $7$ is $$2+5\cdot 50+3\cdot 50=402\equiv 3\pmod{7}\,.$$ Then, you try this with other primes. Commented Jul 23, 2020 at 15:06
• Following my comment above, we know that if a prime natural number $r$ divides $p$, then $r>7$. We now try $r=11$. The sequence $3^{2^k}$ modulo $11$ for $k=0,1,2,3,\ldots$ is $$3,9,4,5,3,9,4,5,3,9,4,5,\ldots\,.$$ Therefore, $\dfrac{1}{3^{2^k}+1}$ for $k=0,1,2,3,\ldots$ are $$3,10,9,2,3,10,9,2,3,10,9,2,\ldots\,.$$ Consequently, $$S\equiv 3+(10+9+2+3)\cdot 25=603\equiv 9 \pmod{11}\,.$$ Therefore, $r>11$ as well. There are only seven primes $13$, $17$, $19$, $23$, $29$, $31$, and $37$ left to check. Commented Jul 23, 2020 at 15:13
• Now, it is easy to see that $$S\equiv 10+(4+10)\cdot 50=710\equiv 8\pmod{13}\,.$$ Thus, $r>13$. Also, $17$ divides the denominator of the third term $\dfrac{1}{3^{2^3}+1}$ of $S$, but not the denominator of any other terms. Therefore, $r>17$. Commented Jul 23, 2020 at 15:39
• Next, \begin{align}S&\equiv 5+(2+16+11+18+4+9)\cdot16+(2+16+11+18)\\&=1012\equiv 5\pmod{19}\,,\end{align} \begin{align}S&\equiv 6+(7+ 16+10+ 5+ 18+ 17+ 8+ 14+ 19+ 6)\cdot10\\&=1206\equiv 10\pmod{23}\,,\end{align} \begin{align}S\equiv 22+3+ (23+11+ 18)\cdot 33=1741 \equiv 1\pmod{29}\,,\end{align} and $$S\equiv 8+(28+14+3+15)\cdot 25=1533\equiv 14\pmod{31}\,.$$ Ergo, $r>31$. Commented Jul 23, 2020 at 15:40
• Finally, \begin{align}S&\equiv 28+(26+14+ 20+ 12+ 24+ 18)\cdot 16+26+14+20+12\\&=1924\equiv 0\pmod{37}\,.\end{align} Therefore, $r=37$ is the smallest prime natural number that divides $p$. I think you can accept WhatsUp's answer now. If you are curious how I obtained the numbers above, play around with this WolframAlpha query. Commented Jul 23, 2020 at 15:41

I'm not sure what kind of problem this is.

It seems that the problem is not intended to be done by hand.

If we denote by $$S(n)$$ the number $$\displaystyle\sum_{k = 0}^n \frac 1{3^{2^k} + 1}$$, then the first several values of the numerator of $$S(n)$$ look like this:

1
7
3^3 * 11
974867
20982415713197
3 * 6480139987906036648979676749
13 * 25220504737903 * 1202418613506277 * 84660948985522106511557529679
149 * 883 * 126001 * 11868766710884224982021663692780373317124689104200960317897970407656906279023556512105818421377935790975902821


Of course, it is easy to show that $$3$$ divides the numerator if $$n \equiv 2 \pmod 3$$. This would be a much more reasonable exercise in elementary number theory.

However we have here $$n = 100$$. This leads to something without a pattern.

With the help of some computer algebra system, I am able to find that the smallest prime factor of the numerator is $$37$$. This is done by checking all primes up to $$37$$ one by one. So it is not really doable with paper and pencil.

• Thank you for your answer. I too fail to see the point of this question, especially without context. Commented Jul 23, 2020 at 14:43
• @Whatsup, thank you sir for your answer. Found this question on a local magazine. If everything remains alright, then they will publish the answers to the various problems, next month. Commented Jul 23, 2020 at 15:09
• OK, perhaps you can share the answer with us next month! Commented Jul 23, 2020 at 15:11
• Sure sir. If they publish the respective answer, I'll update here. (I have observed that sometimes they don't publish some answers, it might be that they couldn't find an answer) Hopefully they'll publish the answer to this question. Commented Jul 23, 2020 at 15:19