When does $2^{2m}+2^m+1$ divide $10^{2m}+10^m+1$?

For what values of $m\in \Bbb N$ is it true that $2^{2m}+2^m+1$ divides $10^{2m}+10^m+1$?

I have it false for $m=1,3$ and true for $m=2,4$

This arises from my thoughts on the question How to find all binary numbers in base $10$ s.t. that its divisible by its own numerical value in base $2$?

• have you tried re-expressing the second one using the factoring of 10 into 2 and 5 ? that may give insight. – user451844 Sep 22 '17 at 16:15
• For all $m \leq 30000$ the only $m$ are $m=0,2,4$. – Ahmad Sep 22 '17 at 16:19
• It may be useful: $$4^m+2^m+1 \mid 100^m+10^m+1-(4^m+2^m+1)(10^m-2^m+1)=4^m(5^m-2^m)(5^m-1) \implies 4^m+2^m+1\mid (5^m-2^m)(5^m-1)$$ – timon92 Sep 22 '17 at 17:33
• @Ahmad can you describe how you found this result? thanks – Joffan Sep 22 '17 at 19:32

Partial result covering approximately two thirds of all the numbers $m$.

I am looking for a covering set of primes. The idea is that whenever we find a prime $p$ such that $p\mid 4^m+2^m+1$ but $p\nmid 100^m+10^m+1$ we have shown that $4^m+2^m+1\nmid 100^m+10^m+1$. When hunting for suitable primes $p$ we can simply look at the factorizations of these numbers. For $p>3$ to be a factor of $k^{2m}+k^m+1=(k^{3m}-1)/(k^m-1)$ we see that $k^m$ has to be a primitive third root of unity modulo $p$. We obviously apply this to both $k=2$ and $k=10$.

To get those primitive third roots of unity we need $\ell=\operatorname{ord}_p(2)$ to be divisible by three. If $\ell=3u$ we then see that $p\mid 4^m+2^m+1$ if and only if $m\equiv u,2u\pmod{3u}$. But, if $t=\operatorname{ord}_p(10)$ is also divisible by three, say $t=3v$, we also have that $p\mid 100^m+10^m+1$ whenever $m\equiv v,2v\pmod{3v}$. Anyway, this allows to conclude that $m$ cannot be in certain residue classes modulo $3w$ where $w=\operatorname{lcm}(u,v)$. Observe that if $t$ is not a multiple of three, then $100^m+10^m+1$ is never divisible by $p$, because $10^m$ is then never a primitive third root of unity.

Getting our hands dirty we see that:

• With $p=7$ we have $\ell=3$ and $t=6$, both divisible by three. This means that when $m\equiv1,5\pmod6$ we have $7\mid 4^m+2^m+1$ and $7\nmid 100^m+10^m+1$.
• With $p=73\mid 2^9-1$ we have $\ell=9=3\cdot3$ and $t=8$. This means that $73\mid 4^m+2^m+1$ iff $m\equiv3,6\pmod9$. But $100^m+10^m+1$ is never divisible by $73$ so we have covered these values of $m$. At this point we have excluded $10$ out of $18$ residue classes modulo $18$, so we have covered more than half the integers.
• The prime $p=13$ is a factor of $2^{12}-1$ and $\ell=12$. But here $t=6$ is a factor of $\ell$. This is bad news for us. No values of $m$ can be excluded. For if $m\equiv4,8\pmod{12}$ then automatically $m\equiv2,4\pmod{6}$. In these cases $13$ is a common factor of both $4^m+2^m+1$ and $100^m+10^m+1$. The same thing happens whenever $2$ is a primitive root modulo $p$. We really need to look for non-primitive cases.
• With $p=151\mid 2^{15}-1$ we have $\ell=15=3\cdot5$. Here $t=75=3\cdot25$. This means that we can rule out $m$, if $m\equiv5,10\pmod{15}$ and $m\not\equiv25,50\pmod{75}$.
• With $p=241\mid 2^{24}-1$ we have $\ell=24=3\cdot8$. Here $t=30=3\cdot10$. We can rule ouf $m$, if $m\equiv8,16\pmod{24}$ and $m\not\equiv10,20\pmod{30}$.

At this point we have ruled out $1216$ residue classes modulo $1800$, so we reached the two thirds point. That modulus $1800$ is the least common multiple of $6,9,75,24$ and $30$ that all appeared above. Recalling that $m=0,2,4$ are solutions the smallest values of $m$ that we have not yet covered are $m=9,14,18,22$. Stopping here for now.

• Concentrating on individual prime factors seems to be inefficient here, and we may never reach the goal. I did learn a few relevant things while typing this answer, so it didn't go to waste irrespective of whether this is useful. – Jyrki Lahtonen Sep 22 '17 at 18:46
• revised list; up to m=100, all but three of the odd m give coprime raw numbers for 2 and 10; even for the m=25, 33, 67, the gcd is small. This might matter as $x^{4t} + x^{2t} + 1 = (x^{2t} + x^t + 1) (x^{2t} - x^t + 1),$ and one can see in the list how prime factors repeat from some $m$ to $2m$ and $4m$ – Will Jagy Sep 22 '17 at 19:55
• Yes @WillJagy. That factorization plays a role. In my (equivalent?) thinking it would go like: if $\omega$ is a primitive third root of unity modulo a prime, then so are $\omega^2$, $\omega^4$, $\omega^8$ etc. – Jyrki Lahtonen Sep 22 '17 at 20:02
• Handling $m=9$ like this would go as follows. $p=262657=4^9+2^9+1$ is a prime. It is easy to see that $10$ is a primitive root of unity modulo $p$, but obviously $p\mid2^{27}-1$. It follows that $m\equiv9,18\pmod{27}$ are covered unless $m$ also happens to be a multiple of $(p-1)/3=87552$. This takes us close to the 75 per cent mark (unless I made a mistake we are then at coverage rate of $0.749622$) – Jyrki Lahtonen Sep 22 '17 at 20:28
• Yes, it may be more efficient to try and exclude small $m$s even though the primes then become bigger. Multiples of $7$ can be excluded unless they are also multiples of $21$ or $112$ with $p=337$. But, it's getting close to midnight. – Jyrki Lahtonen Sep 22 '17 at 20:48

up to 100, the odd $m$ for which the 2 number and the 10 number are not coprime are $m=25,33,67,$ while these gcd's are still quite small compared with the raw numbers.

1
111 = 3  37
7 =  7
1  GCD 1  m  is ODD

2
10101 = 3 7 13  37
21 = 3  7
2  GCD 21
DIVIDES

3
1001001 = 3  333667
73 =  73
3  GCD 1  m  is ODD

4
100010001 = 3 7 13 37  9901
273 = 3 7  13
4  GCD 273
DIVIDES

5
10000100001 = 3 31 37  2906161
1057 = 7  151
5  GCD 1  m  is ODD

6
1000001000001 = 3 19 52579  333667
4161 = 3 19  73
6  GCD 57

7
100000010000001 = 3 37 43 1933  10838689
16513 = 7^2  337
7  GCD 1  m  is ODD

8
10000000100000001 = 3 7 13 37 9901  99990001
65793 = 3 7 13  241
8  GCD 273

9
1000000001000000001 = 3 757  cdot mbox{BIG}
262657 =  262657
9  GCD 1  m  is ODD

10
100000000010000000001 = 3 7 13 31 37 211 241 2161  2906161
1049601 = 3 7 151  331
10  GCD 21

11
10000000000100000000001 = 3 37 67  cdot mbox{BIG}
4196353 = 7  599479
11  GCD 1  m  is ODD

12
1000000000001000000000001 = 3 19 52579 333667  999999000001
16781313 = 3 19 37 73  109
12  GCD 57

13
100000000000010000000000001 = 3 37  cdot mbox{BIG}
67117057 = 7 79  121369
13  GCD 1  m  is ODD

14
10000000000000100000000000001 = 3 7^2 13 37 43 127 1933 2689 459691  10838689
268451841 = 3 7^2 337  5419
14  GCD 147

15
1000000000000001000000000000001 = 3 238681 333667  cdot mbox{BIG}
1073774593 = 73 631  23311
15  GCD 1  m  is ODD

16
100000000000000010000000000000001 = 3 7 13 37 9901  cdot mbox{BIG}
4295032833 = 3 7 13 97 241  673
16  GCD 273

17
10000000000000000100000000000000001 = 3 37 613 210631  cdot mbox{BIG}
17180000257 = 7 103 2143  11119
17  GCD 1  m  is ODD

18
1000000000000000001000000000000000001 = 3 757  cdot mbox{BIG}
68719738881 = 3 87211  262657
18  GCD 3

19
100000000000000000010000000000000000001 = 3 37 21319  cdot mbox{BIG}
274878431233 = 7 32377  1212847
19  GCD 1  m  is ODD

20
10000000000000000000100000000000000000001 = 3 7 13 31 37 61 211 241 2161 9901  cdot mbox{BIG}
1099512676353 = 3 7 13 61 151 331  1321
20  GCD 16653

21
1000000000000000000001000000000000000000001 = 3 10837 23311 45613 333667  cdot mbox{BIG}
4398048608257 = 73 92737  649657
21  GCD 1  m  is ODD

22
100000000000000000000010000000000000000000001 = 3 7 13 37 67  cdot mbox{BIG}
17592190238721 = 3 7 67 20857  599479
22  GCD 1407

23
10000000000000000000000100000000000000000000001 = 3 37 277  cdot mbox{BIG}
70368752566273 = 7  cdot mbox{BIG}
23  GCD 1  m  is ODD

24
1000000000000000000000001000000000000000000000001 = 3 19 3169 52579 98641 333667  cdot mbox{BIG}
281474993487873 = 3 19 37 73 109 433  38737
24  GCD 57

25
100000000000000000000000010000000000000000000000001 = 3 31 37 151 4201  cdot mbox{BIG}
1125899940397057 = 7 151 100801  10567201
25  GCD 151  m  is ODD

26
10000000000000000000000000100000000000000000000000001 = 3 7 13^2 37 157 6397 216451  cdot mbox{BIG}
4503599694479361 = 3 7 79 121369  22366891
26  GCD 21

27
1000000000000000000000000001000000000000000000000000001 = 3 163 9397  cdot mbox{BIG}
18014398643699713 = 2593 71119  97685839
27  GCD 1  m  is ODD

28
100000000000000000000000000010000000000000000000000000001 = 3 7^2 13 37 43 127 1933 2689 9901 226549 459691  cdot mbox{BIG}
72057594306363393 = 3 7^2 13 337 1429 5419  14449
28  GCD 1911

29
10000000000000000000000000000100000000000000000000000000001 = 3 37 4003 72559  cdot mbox{BIG}
288230376688582657 = 7 4177  cdot mbox{BIG}
29  GCD 1  m  is ODD

30
1000000000000000000000000000001000000000000000000000000000001 = 3 19 29611 52579 238681 333667  cdot mbox{BIG}
1152921505680588801 = 3 19 73 631 23311  18837001
30  GCD 57

31
100000000000000000000000000000010000000000000000000000000000001 = 3 37  cdot mbox{BIG}
4611686020574871553 = 7  cdot mbox{BIG}
31  GCD 1  m  is ODD

32
10000000000000000000000000000000100000000000000000000000000000001 = 3 7 13 37 97 9901 206209  cdot mbox{BIG}
18446744078004518913 = 3 7 13 97 193 241 673  22253377
32  GCD 26481

33
1000000000000000000000000000000001000000000000000000000000000000001 = 3 199 397 34849 333667  cdot mbox{BIG}
73786976303428141057 = 73 199 153649  33057806959
33  GCD 199  m  is ODD

34
100000000000000000000000000000000010000000000000000000000000000000001 = 3 7 13 37 613 210631  cdot mbox{BIG}
295147905196532695041 = 3 7 103 307 2143 2857 6529  11119
34  GCD 21

35
10000000000000000000000000000000000100000000000000000000000000000000001 = 3 31 37 43 1933  cdot mbox{BIG}
1180591620751771041793 = 7^2 151 337 29191 106681  152041
35  GCD 1  m  is ODD

36
1000000000000000000000000000000000001000000000000000000000000000000000001 = 3 109 757 153469  cdot mbox{BIG}
4722366482938364690433 = 3 87211 246241 262657  279073
36  GCD 3

37
100000000000000000000000000000000000010000000000000000000000000000000000001 = 3 37^2  cdot mbox{BIG}
18889465931616019808257 = 7 321679  cdot mbox{BIG}
37  GCD 1  m  is ODD

38
10000000000000000000000000000000000000100000000000000000000000000000000000001 = 3 7 13 37 21319  cdot mbox{BIG}
75557863726189201326081 = 3 7 571 32377  cdot mbox{BIG}
38  GCD 21

39
1000000000000000000000000000000000000001000000000000000000000000000000000000001 = 3 333667  cdot mbox{BIG}
302231454904207049490433 = 73 937 6553 86113  7830118297
39  GCD 1  m  is ODD

40
100000000000000000000000000000000000000010000000000000000000000000000000000000001 = 3 7 13 31 37 61 211 241 2161 9901  cdot mbox{BIG}
1208925819615728686333953 = 3 7 13 61 151 241 331 1321  4562284561
40  GCD 4013373

41
10000000000000000000000000000000000000000100000000000000000000000000000000000000001 = 3 37  cdot mbox{BIG}
4835703278460715722080257 = 7  cdot mbox{BIG}
41  GCD 1  m  is ODD

42
1000000000000000000000000000000000000000001000000000000000000000000000000000000000001 = 3 19 10837 23311 45613 52579 333667  cdot mbox{BIG}
19342813113838464841809921 = 3 19 73 92737 649657  77158673929
42  GCD 57

43
100000000000000000000000000000000000000000010000000000000000000000000000000000000000001 = 3 37  cdot mbox{BIG}
77371252455345063274217473 = 7  cdot mbox{BIG}
43  GCD 1  m  is ODD

44
10000000000000000000000000000000000000000000100000000000000000000000000000000000000000001 = 3 7 13 37 67 9901  cdot mbox{BIG}
309485009821362660910825473 = 3 7 13 67 20857 312709 599479  4327489
44  GCD 18291

45
1000000000000000000000000000000000000000000001000000000000000000000000000000000000000000001 = 3 757  cdot mbox{BIG}
1237940039285415459271213057 = 271 262657 348031  cdot mbox{BIG}
45  GCD 1  m  is ODD

46
100000000000000000000000000000000000000000000010000000000000000000000000000000000000000000001 = 3 7 13 37 277 31051  cdot mbox{BIG}
4951760157141591468340674561 = 3 7 139  cdot mbox{BIG}
46  GCD 21

47
10000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000001 = 3 37 283  cdot mbox{BIG}
19807040628566225135874342913 = 7  cdot mbox{BIG}
47  GCD 1  m  is ODD

48
1000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000001 = 3 19 3169 8929 52579 98641 333667  cdot mbox{BIG}
79228162514264619068520660993 = 3 19 37 73 109 433 577 38737  487824887233
48  GCD 57

49
100000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000001 = 3 37 43 1933 63799  cdot mbox{BIG}
316912650057057913324129222657 = 7^3 337  cdot mbox{BIG}
49  GCD 1  m  is ODD

50
10000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000001 = 3 7 13 31 37 151 211 241 2161 4201  cdot mbox{BIG}
1267650600228230527396610048001 = 3 7 151 331 100801  cdot mbox{BIG}
50  GCD 3171

51
1000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000001 = 3 307 18973 333667  cdot mbox{BIG}
5070602400912919857786626506753 = 73 919  cdot mbox{BIG}
51  GCD 1  m  is ODD

52
100000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000001 = 3 7 13^2 37 157 3121 6397 9901 216451  cdot mbox{BIG}
20282409603651674927546878656513 = 3 7 13^2 79 313 1249 3121 21841 121369  22366891
52  GCD 11076429

53
10000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000001 = 3 37 351391  cdot mbox{BIG}
81129638414606690702988259885057 = 7 6679  cdot mbox{BIG}
53  GCD 1  m  is ODD

54
1000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000001 = 3 163 1459 9397  cdot mbox{BIG}
324518553658426744797554530058241 = 3 163 2593 71119 135433  cdot mbox{BIG}
54  GCD 489

55
100000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000001 = 3 31 37 67 471241  cdot mbox{BIG}
1298074214633706943161421101268993 = 7 151 599479  cdot mbox{BIG}
55  GCD 1  m  is ODD

56
10000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000001 = 3 7^2 13 37 43 127 1933 2689 9901 226549 459691  cdot mbox{BIG}
5192296858534827700588090367148033 = 3 7^2 13 241 337 1429 3361 5419 14449  88959882481
56  GCD 1911

57
1000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000001 = 3 333667  cdot mbox{BIG}
20769187434139310658237173392736257 = 73  cdot mbox{BIG}
57  GCD 1  m  is ODD

58
100000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000001 = 3 7 13 37 4003 72559  cdot mbox{BIG}
83076749736557242344718317419233281 = 3 7 4177  cdot mbox{BIG}
58  GCD 21

59
10000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000001 = 3 37 3187  cdot mbox{BIG}
332306998946228968802412517373509633 = 7 184081  cdot mbox{BIG}
59  GCD 1  m  is ODD

60
1000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000001 = 3 19 181 29611 52579 238681 333667  cdot mbox{BIG}
1329227995784915874056728564887191553 = 3 19 37 73 109 181 631 23311 54001  cdot mbox{BIG}
60  GCD 10317

61
100000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000001 = 3 37  cdot mbox{BIG}
5316911983139663493921071250335072257 = 7 367 55633  cdot mbox{BIG}
61  GCD 1  m  is ODD

62
10000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000001 = 3 7 13 37 373 44641  cdot mbox{BIG}
21267647932558653971072598982912901121 = 3 7  cdot mbox{BIG}
62  GCD 21

63
1000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000001 = 3 757  cdot mbox{BIG}
85070591730234615875067023894796828673 = 262657  cdot mbox{BIG}
63  GCD 1  m  is ODD

64
100000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001 = 3 7 13 37 97 193 769 9901 206209  cdot mbox{BIG}
340282366920938463481821351505477763073 = 3 7 13 97 193 241 673  cdot mbox{BIG}
64  GCD 5110833

65
10000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000001 = 3 31 37 1951  cdot mbox{BIG}
1361129467683753853890391917874491949057 = 7 79 151 121369  cdot mbox{BIG}
65  GCD 1  m  is ODD

66
1000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000001 = 3 19 199 397 34849 52579 333667  cdot mbox{BIG}
5444517870735015415487780695203129589761 = 3 19 73 199 5347 153649  cdot mbox{BIG}
66  GCD 11343

67
100000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000001 = 3 37 1609  cdot mbox{BIG}
21778071482940061661803548828222841946113 = 7 1609 22111  cdot mbox{BIG}
67  GCD 1609  m  is ODD

68
10000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000001 = 3 7 13 37 409 613 3061 9901 210631  cdot mbox{BIG}
87112285931760246646919047407712014958593 = 3 7 13 103 307 409 2143 2857 3061 6529 11119 13669  1326700741
68  GCD 341782077

69
1000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000001 = 3 333667  cdot mbox{BIG}
348449143727040986587085893820489354182657 = 73 79903  cdot mbox{BIG}
69  GCD 1  m  is ODD

70
100000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000001 = 3 7^2 13 31 37 43 127 211 241 1933 2161 2689 459691  cdot mbox{BIG}
1393796574908163946347162983661240005427201 = 3 7^2 151 211 331 337 5419 29191 106681 152041 664441  1564921
70  GCD 31017

71
10000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000001 = 3 37 853  cdot mbox{BIG}
5575186299632655785386290751403525199101953 = 7 66457  cdot mbox{BIG}
71  GCD 1  m  is ODD

72
1000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000001 = 3 109 757 153469  cdot mbox{BIG}
22300745198530623141540440639131231151194113 = 3 87211 246241 262657 279073  cdot mbox{BIG}
72  GCD 3

73
100000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000001 = 3 37 439  cdot mbox{BIG}
89202980794122492566152317823559185314349057 = 7 3943  cdot mbox{BIG}
73  GCD 1  m  is ODD

74
10000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000001 = 3 7 13 37^2 223 4663  cdot mbox{BIG}
356811923176489970264590381828305262676541441 = 3 7 3331 17539 321679  cdot mbox{BIG}
74  GCD 21

75
1000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 238681 333667  cdot mbox{BIG}
1427247692705959881058323748381358093544456193 = 73 631 23311 115201 617401  cdot mbox{BIG}
75  GCD 1  m  is ODD

76
100000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 7 13 37 229 2281 4789 9901 21319  cdot mbox{BIG}
5708990770823839524233219435661706459854405633 = 3 7 13 571 32377 131101 160969  cdot mbox{BIG}
76  GCD 273

77
10000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 37 43 67 1933 2311  cdot mbox{BIG}
22835963083295358096932726626919374010770784257 = 7^2 337 463 599479  cdot mbox{BIG}
77  GCD 1  m  is ODD

78
1000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 19 52579 333667 461917  cdot mbox{BIG}
91343852333181432387730604276222592385789460481 = 3 19 73 937 6553 86113  cdot mbox{BIG}
78  GCD 57

79
100000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 37  cdot mbox{BIG}
365375409332725729550921812641980562228570488833 = 7 1423 49297  cdot mbox{BIG}
79  GCD 1  m  is ODD

80
10000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 7 13 31 37 61 211 241 2161 9901  cdot mbox{BIG}
1461501637330902918203686041642102634285107249153 = 3 7 13 61 97 151 241 331 673 1321  cdot mbox{BIG}
80  GCD 4013373

81
1000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3  cdot mbox{BIG}
5846006549323611672814741748716771307882079584257 = 487  cdot mbox{BIG}
81  GCD 1  m  is ODD

82
100000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 7 13 37 739 148339  cdot mbox{BIG}
23384026197294446691258962159163806773011619512321 = 3 7 739 165313  cdot mbox{BIG}
82  GCD 15519

83
10000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 37 4483  cdot mbox{BIG}
93536104789177786765035838965248670175013080399873 = 7  cdot mbox{BIG}
83  GCD 1  m  is ODD

84
1000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 19 1009 10837 23311 45613 52579 333667  cdot mbox{BIG}
374144419156711147060143336518181566865985526300673 = 3 19 37 73 109 92737 649657  cdot mbox{BIG}
84  GCD 57

85
100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 31 37 613 210631  cdot mbox{BIG}
1496577676626844588240573307387100039795808514605057 = 7 103 151 2143 11119 106591 949111  cdot mbox{BIG}
85  GCD 1  m  is ODD

86
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 7 13 37  cdot mbox{BIG}
5986310706507378352962293152177147703846966877224961 = 3 7 1033  cdot mbox{BIG}
86  GCD 21

87
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 523 333667 670249  cdot mbox{BIG}
23945242826029513411849172453966085904715333146509313 = 73  cdot mbox{BIG}
87  GCD 1  m  is ODD

88
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 7 13 37 67 2377 9901 16369 432961  cdot mbox{BIG}
95780971304118053647396689506379333797516263861256193 = 3 7 13 67 241 7393 20857 312709 599479  cdot mbox{BIG}
88  GCD 18291

89
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 37 9613  cdot mbox{BIG}
383123885216472214589586757406547315547374917995462657 = 7  cdot mbox{BIG}
89  GCD 1  m  is ODD

90
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 757 6481  cdot mbox{BIG}
1532495540865888858358347028388249222904119397082726401 = 3 271 811 15121 87211 262657 348031  cdot mbox{BIG}
90  GCD 3

91
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 37 43 1093 1933  cdot mbox{BIG}
6129982163463555433433388111077116813045717038532657153 = 7^2 79 337 121369  cdot mbox{BIG}
91  GCD 1  m  is ODD

92
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 7 13 37 277 829 9901 31051  cdot mbox{BIG}
24519928653854221733733552439356707095041347054534131713 = 3 7 13 139  cdot mbox{BIG}
92  GCD 273

93
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 333667  cdot mbox{BIG}
98079714615416886934934209747523308065882346018943533057 = 73 16183 34039  cdot mbox{BIG}
93  GCD 1  m  is ODD

94
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 7 13 37 283 344887  cdot mbox{BIG}
392318858461667547739736838970286191634963299677388144641 = 3 7  cdot mbox{BIG}
94  GCD 21

95
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 31 37 21319  cdot mbox{BIG}
1569275433846670190958947355841530685282721029912780603393 = 7 151 32377  cdot mbox{BIG}
95  GCD 1  m  is ODD

96
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 19 3169 8929 13249 52579 98641 333667  cdot mbox{BIG}
6277101735386680763835789423286894578616619782057578463233 = 3 19 37 73 109 433 577 1153 6337 38737  cdot mbox{BIG}
96  GCD 57

97
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 37 1747 18043  cdot mbox{BIG}
25108406941546723055343157692989121989437950453043225952257 = 7 272959  cdot mbox{BIG}
97  GCD 1  m  is ODD

98
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 7^3 13 37 43 127 1933 2689 63799 459691  cdot mbox{BIG}
100433627766186892221372630771639575307694744461798728007681 = 3 7^3 337 5419 748819  cdot mbox{BIG}
98  GCD 1029

99
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 757 55243 198397  cdot mbox{BIG}
401734511064747568885490523085924475930664863146446560428033 = 262657  cdot mbox{BIG}
99  GCD 1  m  is ODD

100
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 = 3 7 13 31 37 61 151 211 241 601 2161 4201 9901 261301  cdot mbox{BIG}
1606938044258990275541962092342430253122431223184289538506753 = 3 7 13 61 151 331 1201 1321 63901 100801  cdot mbox{BIG}
100  GCD 2514603


partial answer: using my comment we get:
\begin{align} \\ 2^{2m}+2^m+1 &\mid 2^{2m}5^{2m}+2^m5^m+1 \\ &\implies 2^{2m}+2^m+1 \mid 2^{2m}(5^{2m}-1)+2^m(5^m-1) \\ &\implies 2^{2m}+2^m+1 \mid 2^m\big({5^{2m}-1\over 4}\big)+\big({5^m-1\over 4}\big) \\ &\implies 2^m(2^m+1)+1 \mid 2^m\big({5^{2m}-1\over 4}\big)+\big({5^m-1\over 4}\big) \end{align}

hope this helps simplify things. edit: the fractions are the base 5 repunits.

LATE Edit: if M is divisible by totient function values you can also use Euler's theorem to prove that both are 3 mod what ever numbers give those totients. then it's about when two numbers on arithmetic progressions divide each other.