Number Theory or Algebra?

Question

Prove that if $4^m-2^m+1$ is a prime number, then all the prime divisors of $m$ are smaller than $5$

I initially thought about putting $4^m-2^m+1=p$ where $p$ is some prime and after eliminating initial cases of $p<5$ , setting $p=6k \pm 1$. However, since I'm just a beginner in Number Theory, I couldn't figure out anything else. What is more surprising that my teacher gave this problem in an Algebra worksheet, so perhaps there is some good algebraic way to do this.

So, thinking on Algebraic lines, I made a substitution $2^m=x$ and did some manipulations to the quadratic thus made. However, still no luck (despite the fact that I'm pretty confident about my Algebraic skills) I look forward for some help with this one. Any (or both) method will do. Thanks in advance!

Answer 1

Note that $$ 4^m-2^m+1=\frac{8^m+1}{2^m+1} $$ so that when $m=pq$ is composite, there will be additional factors $4^p-2^p+1$ and $4^q-2^q+1$ to consider.

Answer 2

Taking $A_m = 4^m - 2^m + 1,$ when $m$ is odd we find $A_m \equiv 0 \pmod 3$ anyway.

Apparently, when $n$ is odd and not divisible by $3,$ and for any $k \geq 1,$

$$ A_{2^k} \; | \; A_{2^k n} \; \;. $$

In defense of this, I have, so far, from the answer by LutzL, $$ A_{2^k n} = \frac{8^{2^k n} + 1}{2^{2^k n} + 1} = \frac{8^{2^k } + 1}{2^{2^k } + 1} \cdot \frac{\mbox{stuff}}{\mbox{other stuff}} = A_{2^k } \cdot \mbox{integer?} $$

The output below has $m$ even but not divisible by $3.$ Note that we do have some factors for $A_{160}$ but not for $A_{224}.$ Both should be divisible by $A_{32},$ which is, apparently, prime. Oh, I told the machine to do trial division with primes up to 30,000,000.

One test that can be done without taking very long is to let $m$ get much larger but not divisible by $3,$ and have the values of $A_2, A_4, A_8, A_{16}, A_{32},$ and so on ready. Without factoring anything, write any $m = 2^k n$ with $n$ odd, then check that $A_m \equiv 0 \pmod {A_{2^k}}.$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

2   13 = 13
4   241 = 241
8   65281 = 97 673
10   1047553 = 13 cdot 61 1321
14   268419073 = 13 cdot 1429 14449
16   4294901761 = 193 22253377
20   1099510579201 = 241  cdot  mbox{BIG} 
22   17592181850113 = 13 cdot 312709 4327489
26   4503599560261633 = 13^2 cdot 313 cdot 1249 cdot 3121 21841     
28   72057593769492481 = 241 cdot 3361  cdot  mbox{BIG} 
32   18446744069414584321 =  cdot  mbox{BIG} 
34   295147905162172956673 = 13 cdot 409 cdot 3061 cdot 13669  cdot  mbox{BIG} 
38   75557863725639445512193 = 13 cdot 131101 cdot 160969  cdot  mbox{BIG} 
40   1208925819613529663078401 = 97 cdot 673  cdot  mbox{BIG} 
44    = 241 cdot 7393  cdot  mbox{BIG} 
46    = 13  cdot  mbox{BIG} 
50    = 13 cdot 61 cdot 1201 cdot 1321 cdot 63901 cdot 13334701  cdot  mbox{BIG} 
52    = 241  cdot  mbox{BIG} 
56    = 97 cdot 673 cdot 2017  cdot  mbox{BIG} 
58    = 13 cdot 349 cdot 29581  cdot  mbox{BIG} 
62    = 13 cdot 373  cdot  mbox{BIG} 
64    = 769  cdot  mbox{BIG} 
68    = 241 cdot 8161  cdot  mbox{BIG} 
70    = 13 cdot 61 cdot 421 cdot 1321 cdot 1429 cdot 14449  cdot  mbox{BIG} 
74    = 13 cdot 3109  cdot  mbox{BIG} 
76    = 241 cdot 90289  cdot  mbox{BIG} 
80    = 193 cdot 23041 cdot 22253377  cdot  mbox{BIG} 
82    = 13 cdot 2953  cdot  mbox{BIG} 
86    = 13 cdot 17029 cdot 46957  cdot  mbox{BIG} 
88    = 97 cdot 673  cdot  mbox{BIG} 
92    = 241  cdot  mbox{BIG} 
94    = 13 cdot 1129 cdot 5641 cdot 1768141  cdot  mbox{BIG} 
98    = 13 cdot 1429 cdot 14449 cdot 540961  cdot  mbox{BIG} 
100    = 241  cdot  mbox{BIG} 
104    = 97 cdot 673 cdot 4993 cdot 94849  cdot  mbox{BIG} 
106    = 13 cdot 10177 cdot 207973  cdot  mbox{BIG} 
110    = 13 cdot 61 cdot 661 cdot 1321 cdot 3301 cdot 8581 cdot 312709 cdot 4327489  cdot  mbox{BIG} 
112    = 193 cdot 22253377  cdot  mbox{BIG} 
116    = 241 cdot 82129  cdot  mbox{BIG} 
118    = 13 cdot 709 cdot 12037 cdot 31153 cdot 5397793  cdot  mbox{BIG} 
122    = 13 cdot 5080081  cdot  mbox{BIG} 
124    = 241 cdot 1489 cdot 29761  cdot  mbox{BIG} 
128    =  cdot  mbox{BIG} 
130    = 13^2 cdot 61 cdot 313 cdot 1249 cdot 1321 cdot 2341 cdot 3121 cdot 21841 cdot 468781  cdot  mbox{BIG}      
134    = 13 cdot 3217 cdot 10453 cdot 132661 cdot 192961  cdot  mbox{BIG} 
136    = 97 cdot 673  cdot  mbox{BIG} 
140    = 241 cdot 3361 cdot 127681 cdot 1130641  cdot  mbox{BIG} 
142    = 13 cdot 853 cdot 189997 cdot 266677 cdot 1396429 cdot 18369973  cdot  mbox{BIG} 
146    = 13 cdot 877 cdot 1013533  cdot  mbox{BIG} 
148    = 241 cdot 92353 cdot 126097 cdot 532801 cdot 854257  cdot  mbox{BIG} 
152    = 97 cdot 673  cdot  mbox{BIG} 
154    = 13 cdot 1429 cdot 14449 cdot 312709 cdot 4327489  cdot  mbox{BIG} 
158    = 13 cdot 151681  cdot  mbox{BIG} 
160    = 26881 cdot 4855681  cdot  mbox{BIG} 
164    = 241  cdot  mbox{BIG} 
166    = 13 cdot 1993 cdot 136453  cdot  mbox{BIG} 
170    = 13 cdot 61 cdot 409 cdot 1321 cdot 3061 cdot 13669 cdot 51001 cdot 15571321  cdot  mbox{BIG} 
172    = 241 cdot 328177 cdot 359137  cdot  mbox{BIG} 
176    = 193 cdot 22253377  cdot  mbox{BIG} 
178    = 13 cdot 2137  cdot  mbox{BIG} 
182    = 13^2 cdot 313 cdot 1249 cdot 1429 cdot 3121 cdot 14449 cdot 21841 cdot 503413 cdot 1948129  cdot  mbox{BIG}      
184    = 97 cdot 673  cdot  mbox{BIG} 
188    = 241  cdot  mbox{BIG} 
190    = 13 cdot 61 cdot 1321 cdot 131101 cdot 160969 cdot 185821 cdot 247381  cdot  mbox{BIG} 
194    = 13 cdot 580837  cdot  mbox{BIG} 
196    = 241 cdot 3361 cdot 84673  cdot  mbox{BIG} 
200    = 97 cdot 673 cdot 4801 cdot 55201  cdot  mbox{BIG} 
202    = 13 cdot 1213 cdot 1896781 cdot 10838917 cdot 12753877  cdot  mbox{BIG} 
206    = 13 cdot 1237  cdot  mbox{BIG} 
208    = 193 cdot 22253377  cdot  mbox{BIG} 
212    = 241 cdot 12721  cdot  mbox{BIG} 
214    = 13 cdot 57781 cdot 1016929  cdot  mbox{BIG} 
218    = 13 cdot 2617 cdot 5233 cdot 9157  cdot  mbox{BIG} 
220    = 241 cdot 7393 cdot 14736481  cdot  mbox{BIG} 
224    =  cdot  mbox{BIG} 

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Answer 3

I believe that this problem can most easily be addressed in the Eisenstein integers $R = \mathbb{Z}[\omega]$, where $\omega = e^{\frac{2 \pi i}{3}},$ although there may be more elementary approaches. It is well known that this is a principal ideal domain. I claim that $2^{2m}- 2^{m}+1$ can only be prime (in $\mathbb{Z}$) when $m$ has no prime factor greater than $3,$ as the problem asks. For If not write $m = hn$ where $h >1$ is relatively prime to $6,$ and $2$ and $3$ are the only prime factors of $n.$ Then $4^{m} -2^{m} + 1 = (2^{m} + \omega)(2^{m} + \omega^{2})$ in $R.$ If $h \equiv 1$ (mod $3$), notice that $\omega^{h} = \omega$, while if $h \equiv 2$ (mod $3$), notice that $\omega^{h} = \omega^{2}. $ Hence, in the ring $R,$ $2^{m}+ \omega$ is divisible either by $2^{n}+ \omega$ or by $2^{n} + \omega^{2},$ and hence is not a prime element of $R$.Thus $4^{m}-2^{m} +1$ is not a rational prime either.

For the purposes of illustration, the smallest non-trivial case is when $m = 10.$ Then we see by the above method that $2^{10}+\omega$ is divisible by $4+\omega^{2}$ in $R.$ Then we see that $(4+\omega)(4+\omega^{2}) = 13$ divides $2^{20}-2^{10}+1 = (2^{10}+\omega)(2^{10}+ \omega^{2})$ in $\mathbb{Z}.$ We can check this by verifying directly
that $2^{20} - 2^{10} + 1 \equiv 1- (3 \times 2^{8}) \equiv 1-27 \equiv 0$ (mod $13$) .