Divisor of $3^{2n+1}+61$

Question

I have difficulty to show the following:

If $p$ is a prime and $p^2$ divides $3^{2n+1}+61$, then $p$ must be $2$.

I appreciate any help.

Answer 1

First part: is easy to show that $$ 3^{2n+1}+61\equiv 0\pmod 4 $$ why? Well $61\equiv 1 \pmod 4$ (easy to verify). And is also easy to verify that $$ 3^{2n+1}\equiv 3\pmod 4 $$ In fact every odd number can be written as $4k+3$ or $4k+1$ with $k$ integer. Let's suppose that for some $n$ we can write ($3^n$ is odd) $$ 3^n = 4k+3 $$ now we can easily verify that $$ 3^{n+1}=3(4k+3)=4(2+3k)+1 $$ and since $3=4\cdot 0+3$ is easy to see that for every odd power we have $$ 3^{2n+1}=4k+3 $$ and therefore summing (modulus 4) with $61$ you get $$ 3^{2n+1}+61\equiv 3+1\pmod 4\equiv 0 \pmod 4 $$

Now what remains to be shown is that no other prime satisfy what the OP is asking. Working on that now ;-)

EDIT: another nice way to show that (and much shorter) is: let's write $$ g(n)=3^{2n+1}+61 $$ now is easy to see that $$ g(n+1)=3^{2n+1+2}+61=3^{2n+1}3^2+61=3^{2n+1}3^2+3^2 61-8\cdot 61 = g(n)3^2-8\cdot 61 $$ and so is also true that $$ g(n+1) \equiv g(n)3^2-8\cdot 61 \pmod 4 \equiv 0 \pmod 4 $$ and since is true for $n=0$ is true for all $n$.

EDIT 2: let's see if we can move on with the second part. Let's use what I just wrote. Let's suppose that exist a prime $p_2>2$ for which for some $n$ $$ g(n)\equiv 0 \pmod {p_2^2} $$ now let's consider $n+1$ we find that (similar to what we did before) $$ g(n+1)\equiv -8\cdot 61 \pmod {p_2^2} $$ that is not zero. I am actually not sure that is enough... Thinking a bit about this and then I will finish to edit my answer. Of course it could be true for one $n$...

Answer 2

As Will Jagy suspected this is false.

$$17^2\mid 3^{123}+61.$$

Answer 3

Wrote a thing in C++ with GMP that does trial division by primes only up to some bound i provide. So this limited factoring is very fast, and definitive up to that bound; for this run i put in bound = 1000. However, when the final factor is written as "BIG" we do not know the factorization of that.

$$ 3^{123} + 61 = 2^3 \cdot 11 \cdot 17^2 \cdot 467 \cdot \mbox{BIG} $$ $$ 3^{197} + 61 = 2^4 \cdot 23^2 \cdot 761 \cdot \mbox{BIG} $$ $$ 3^{267} + 61 = 2^3 \cdot 17 \cdot 29 \cdot 127^2 \cdot \mbox{BIG} $$ $$ 3^{275} + 61 = 2^3 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{395} + 61 = 2^3 \cdot 17^2 \cdot 23 \cdot 59 \cdot 311 \cdot \mbox{BIG} $$ $$ 3^{617} + 61 = 2^5 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{667} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{683} + 61 = 2^3 \cdot 11 \cdot 17 \cdot 101^2 \cdot \mbox{BIG} $$ $$ 3^{703} + 61 = 2^3 \cdot 11 \cdot 23^2 \cdot \mbox{BIG} $$ $$ 3^{715} + 61 = 2^3 \cdot 17 \cdot 29^2 \cdot \mbox{BIG} $$ $$ 3^{779} + 61 = 2^3 \cdot 17 \cdot 19 \cdot 103^2 \cdot \mbox{BIG} $$ $$ 3^{801} + 61 = 2^6 \cdot 59^2 \cdot \mbox{BIG} $$ $$ 3^{939} + 61 = 2^3 \cdot 17^2 \cdot 29 \cdot \mbox{BIG} $$ $$ 3^{959} + 61 = 2^3 \cdot 19^2 \cdot 613 \cdot \mbox{BIG} $$ $$ 3^{1093} + 61 = 2^4 \cdot 11 \cdot 173^2 \cdot \mbox{BIG} $$ $$ 3^{1209} + 61 = 2^5 \cdot 23^2 \cdot 859 \cdot \mbox{BIG} $$ $$ 3^{1211} + 61 = 2^3 \cdot 17^2 \cdot 19 \cdot \mbox{BIG} $$ $$ 3^{1301} + 61 = 2^4 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{1421} + 61 = 2^4 \cdot 53^2 \cdot \mbox{BIG} $$ $$ 3^{1483} + 61 = 2^3 \cdot 11 \cdot 17^2 \cdot 101 \cdot \mbox{BIG} $$ $$ 3^{1527} + 61 = 2^3 \cdot 29^2 \cdot 103 \cdot 127 \cdot \mbox{BIG} $$ $$ 3^{1643} + 61 = 2^3 \cdot 11 \cdot 17 \cdot 19^2 \cdot 557 \cdot \mbox{BIG} $$ $$ 3^{1715} + 61 = 2^3 \cdot 19 \cdot 23^2 \cdot \mbox{BIG} $$ $$ 3^{1755} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{1829} + 61 = 2^4 \cdot 821^2 \cdot \mbox{BIG} $$ $$ 3^{1831} + 61 = 2^3 \cdot 109^2 \cdot \mbox{BIG} $$ $$ 3^{1985} + 61 = 2^6 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{2027} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{2209} + 61 = 2^6 \cdot 71^2 \cdot 109 \cdot 647 \cdot \mbox{BIG} $$ $$ 3^{2221} + 61 = 2^4 \cdot 23^2 \cdot \mbox{BIG} $$ $$ 3^{2299} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{2327} + 61 = 2^3 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{2339} + 61 = 2^3 \cdot 29^2 \cdot \mbox{BIG} $$ $$ 3^{2571} + 61 = 2^3 \cdot 17^2 \cdot 241 \cdot \mbox{BIG} $$ $$ 3^{2669} + 61 = 2^4 \cdot 19^2 \cdot 53 \cdot \mbox{BIG} $$ $$ 3^{2727} + 61 = 2^3 \cdot 23^2 \cdot \mbox{BIG} $$ $$ 3^{2843} + 61 = 2^3 \cdot 11 \cdot 17^3 \cdot 29 \cdot \mbox{BIG} $$ $$ 3^{3011} + 61 = 2^3 \cdot 19^2 \cdot 29 \cdot \mbox{BIG} $$ $$ 3^{3051} + 61 = 2^3 \cdot 17 \cdot 241^2 \cdot \mbox{BIG} $$ $$ 3^{3115} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{3151} + 61 = 2^3 \cdot 29^2 \cdot 463 \cdot \mbox{BIG} $$ $$ 3^{3233} + 61 = 2^6 \cdot 11 \cdot 23^2 \cdot \mbox{BIG} $$ $$ 3^{3353} + 61 = 2^5 \cdot 11 \cdot 19^2 \cdot 59 \cdot \mbox{BIG} $$ $$ 3^{3387} + 61 = 2^3 \cdot 17^2 \cdot 23 \cdot \mbox{BIG} $$ $$ 3^{3659} + 61 = 2^3 \cdot 17^2 \cdot 19 \cdot \mbox{BIG} $$ $$ 3^{3695} + 61 = 2^3 \cdot 19^2 \cdot 23 \cdot \mbox{BIG} $$ $$ 3^{3739} + 61 = 2^3 \cdot 17 \cdot 23^2 \cdot 29 \cdot \mbox{BIG} $$ $$ 3^{3931} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{3963} + 61 = 2^3 \cdot 11 \cdot 17 \cdot 29^2 \cdot \mbox{BIG} $$ $$ 3^{4037} + 61 = 2^4 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{4177} + 61 = 2^8 \cdot 53^2 \cdot \mbox{BIG} $$ $$ 3^{4203} + 61 = 2^3 \cdot 11 \cdot 17^2 \cdot 439 \cdot \mbox{BIG} $$ $$ 3^{4223} + 61 = 2^3 \cdot 11 \cdot 23 \cdot 59^2 \cdot 613 \cdot \mbox{BIG} $$ $$ 3^{4245} + 61 = 2^4 \cdot 23^2 \cdot \mbox{BIG} $$ $$ 3^{4281} + 61 = 2^5 \cdot 53 \cdot 59 \cdot 103^2 \cdot \mbox{BIG} $$ $$ 3^{4379} + 61 = 2^3 \cdot 17 \cdot 19^2 \cdot 71 \cdot \mbox{BIG} $$ $$ 3^{4475} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{4605} + 61 = 2^4 \cdot 761^2 \cdot \mbox{BIG} $$ $$ 3^{4721} + 61 = 2^7 \cdot 19^3 \cdot \mbox{BIG} $$ $$ 3^{4747} + 61 = 2^3 \cdot 17^2 \cdot 29 \cdot 109 \cdot \mbox{BIG} $$ $$ 3^{4751} + 61 = 2^3 \cdot 23^2 \cdot \mbox{BIG} $$ $$ 3^{4775} + 61 = 2^3 \cdot 19 \cdot 29^2 \cdot \mbox{BIG} $$ $$ 3^{5019} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{5063} + 61 = 2^3 \cdot 11 \cdot 19^2 \cdot 103 \cdot \mbox{BIG} $$ $$ 3^{5257} + 61 = 2^5 \cdot 23^2 \cdot \mbox{BIG} $$ $$ 3^{5291} + 61 = 2^3 \cdot 17^2 \cdot 227 \cdot \mbox{BIG} $$ $$ 3^{5405} + 61 = 2^4 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{5563} + 61 = 2^3 \cdot 11 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{5587} + 61 = 2^3 \cdot 23 \cdot 29^2 \cdot \mbox{BIG} $$ $$ 3^{5747} + 61 = 2^3 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{5763} + 61 = 2^3 \cdot 11 \cdot 23^2 \cdot 163 \cdot \mbox{BIG} $$ $$ 3^{5835} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{6089} + 61 = 2^5 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{6107} + 61 = 2^3 \cdot 17^2 \cdot 19 \cdot \mbox{BIG} $$ $$ 3^{6269} + 61 = 2^4 \cdot 19 \cdot 23^2 \cdot 71 \cdot \mbox{BIG} $$ $$ 3^{6379} + 61 = 2^3 \cdot 17^2 \cdot 23 \cdot \mbox{BIG} $$ $$ 3^{6399} + 61 = 2^3 \cdot 29^2 \cdot \mbox{BIG} $$ $$ 3^{6431} + 61 = 2^3 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{6651} + 61 = 2^3 \cdot 17^2 \cdot 29 \cdot 241 \cdot \mbox{BIG} $$ $$ 3^{6773} + 61 = 2^4 \cdot 11 \cdot 19^2 \cdot 613 \cdot \mbox{BIG} $$ $$ 3^{6775} + 61 = 2^3 \cdot 23^2 \cdot 59 \cdot \mbox{BIG} $$ $$ 3^{6889} + 61 = 2^5 \cdot 89^2 \cdot \mbox{BIG} $$ $$ 3^{6923} + 61 = 2^3 \cdot 11 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{6933} + 61 = 2^4 \cdot 11 \cdot 53^2 \cdot 103 \cdot \mbox{BIG} $$ $$ 3^{7115} + 61 = 2^3 \cdot 17 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{7179} + 61 = 2^3 \cdot 17 \cdot 71^2 \cdot \mbox{BIG} $$ $$ 3^{7195} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{7211} + 61 = 2^3 \cdot 17 \cdot 29^2 \cdot \mbox{BIG} $$ $$ 3^{7281} + 61 = 2^7 \cdot 23^2 \cdot \mbox{BIG} $$ $$ 3^{7457} + 61 = 2^6 \cdot 19^2 \cdot 23 \cdot 173 \cdot \mbox{BIG} $$ $$ 3^{7467} + 61 = 2^3 \cdot 17^3 \cdot \mbox{BIG} $$ $$ 3^{7645} + 61 = 2^4 \cdot 59^2 \cdot 653 \cdot 761 \cdot \mbox{BIG} $$ $$ 3^{7717} + 61 = 2^4 \cdot 109^2 \cdot \mbox{BIG} $$ $$ 3^{7739} + 61 = 2^3 \cdot 17^2 \cdot 71 \cdot 389 \cdot \mbox{BIG} $$ $$ 3^{7783} + 61 = 2^3 \cdot 11 \cdot 101 \cdot 103^2 \cdot 251 \cdot \mbox{BIG} $$ $$ 3^{7787} + 61 = 2^3 \cdot 17 \cdot 23^2 \cdot \mbox{BIG} $$ $$ 3^{7799} + 61 = 2^3 \cdot 19^2 \cdot 29 \cdot \mbox{BIG} $$ $$ 3^{8011} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{8023} + 61 = 2^3 \cdot 11 \cdot 29^2 \cdot 647 \cdot \mbox{BIG} $$ $$ 3^{8141} + 61 = 2^4 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{8283} + 61 = 2^3 \cdot 11 \cdot 17^2 \cdot 59 \cdot 101 \cdot 251 \cdot \mbox{BIG} $$ $$ 3^{8293} + 61 = 2^4 \cdot 11 \cdot 23^2 \cdot 103 \cdot \mbox{BIG} $$ $$ 3^{8483} + 61 = 2^3 \cdot 11 \cdot 19^2 \cdot 101 \cdot 401 \cdot \mbox{BIG} $$ $$ 3^{8555} + 61 = 2^3 \cdot 17^2 \cdot 19 \cdot 29 \cdot \mbox{BIG} $$ $$ 3^{8799} + 61 = 2^3 \cdot 23^2 \cdot \mbox{BIG} $$ $$ 3^{8825} + 61 = 2^5 \cdot 19^2 \cdot 89 \cdot 641 \cdot \mbox{BIG} $$ $$ 3^{8827} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{8835} + 61 = 2^3 \cdot 29^2 \cdot 127 \cdot 937 \cdot \mbox{BIG} $$ $$ 3^{9099} + 61 = 2^3 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{9167} + 61 = 2^3 \cdot 19^2 \cdot 439 \cdot \mbox{BIG} $$ $$ 3^{9305} + 61 = 2^5 \cdot 23^2 \cdot \mbox{BIG} $$ $$ 3^{9371} + 61 = 2^3 \cdot 17^2 \cdot 23 \cdot \mbox{BIG} $$ $$ 3^{9509} + 61 = 2^4 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{9643} + 61 = 2^3 \cdot 11 \cdot 17^2 \cdot \mbox{BIG} $$ $$ 3^{9647} + 61 = 2^3 \cdot 29^2 \cdot 599 \cdot \mbox{BIG} $$ $$ 3^{9689} + 61 = 2^5 \cdot 19 \cdot 53^2 \cdot \mbox{BIG} $$ $$ 3^{9811} + 61 = 2^3 \cdot 23^3 \cdot 227 \cdot \mbox{BIG} $$ $$ 3^{9851} + 61 = 2^3 \cdot 17 \cdot 19^2 \cdot \mbox{BIG} $$ $$ 3^{9915} + 61 = 2^3 \cdot 17^2 \cdot 829 \cdot \mbox{BIG} $$