In OEIS entry A204620, there is a question (by Arkadiusz Wesolowski) about whether composite numbers of the form: $$3\cdot 2^n + 1$$ can be divisors of a Fermat number, i.e. of a number of the form $2^{2^m}+1$. The question is "answered" by a comment by myself where I quote Morehead's 1906 paper (see Links section on OEIS entry). In it, he states:

It is easy to show that composite numbers of the forms $2^\kappa \cdot 3 + 1,\ 2^\kappa \cdot 5 + 1$ can not be factors of Fermat's numbers.

However, to be sure, is that really easy to see? Or can it be proved in a "hard" way?

  • $\begingroup$ @mjqxxxx I do not see the relevance. For example $p=3\cdot 2^{41}+1$ (a prime) is $1$ (mod $3$), just as you say. This $p$ divides the Fermat number $F_{38}$ which is of course $2$ (mod $3$). In this case $p$ is a prime. Could the same happen for a composite divisor of form $3\cdot 2^n+1$? $\endgroup$ Apr 24 '20 at 16:27
  • $\begingroup$ I tried to prove it straight forward, but I failed. For me, it is not at all obvious. $\endgroup$
    – Peter
    Apr 24 '20 at 21:24
  • 1
    $\begingroup$ I asked a smart person, and his initial reply is: "I think I can prove that if $3\cdot 2^n + 1$ is a composite number dividing $F_m$, then $2\log_2(n) < m < (n-5)/2$. That obviously doesn't solve the problem, but it's a pretty strong plausibility argument given how small $n-m$ usually is." Had there been an easy, full argument, it is likely he would have seen it. I will add a bounty to this question now. If someone can answer "There is probably no easy proof" in a sufficiently convincing manner, the bounty shall be theirs. $\endgroup$ Apr 27 '20 at 20:35
  • 1
    $\begingroup$ I have looked into the literature, in particular the book "17 Lectures on Fermat Numbers" which mentions this result of Morehead without proof. Other articles also cite Morehead's work but I have not found any that give a proof. I've also had a go at proving the result and all I can show is: If $q$ is a prime power and $q | 3 \cdot 2^{n} + 1$ where $n = 2^a \cdot b$ such that $gcd(2, b) = 1$, then $ord_q(3) = 2^{m - a + 1}$. I imagine a similar result holds for $q | 5 \cdot 2^n + 1$. $\endgroup$ May 3 '20 at 23:14
  • $\begingroup$ @Ollie In the middle of the short paper, Morehead argues that $2^{75}\cdot 5+1$ must be prime with a bit of detail, namely that no nontrivial factor can have the right form, and this works in this particular case. However, the general statement in the last sentence of the paper has no explanation. $\endgroup$ May 4 '20 at 7:01

Sorry, I wasn't able to complete the proof. I'm sure there are much better ideas, probably involving quadratic residues. I'll post what I have so far just because I thought about it for a few hours, and maybe it'll help someone else answer it.

One can use the fact that every factor of a Fermat number $F_m$ for $m>2$ is of the form $k\cdot 2^{j}+1$, where $k$ is odd and $j>1$. For non-unit factors $j$ must be greater than $0$. (See https://en.wikipedia.org/wiki/Fermat_number#Factorization_of_Fermat_numbers .)

If $3\cdot 2^n+1=ab$ divides $F_m,$ then both $a,b$ must be of the form above. So let $k_1, k_2$ be odd natural numbers and let $j_1,j_2>0$ such that:

$$3\cdot2^n+1=(k_1 \cdot 2^{j_1}+1)(k_2\cdot 2^{j_2}+1)=k_1k_22^{j_1+j_2}+k_12^{j_1}+k_22^{j_2}+1.$$

Assume $j_1\le j_2$. Subtract $1$ and divide by by $2^{j_1}$ on both sides (which is strictly less than $2^n$) to get

$$3\cdot 2^{n-j_1} = k_1k_2 2^{j_2}+k_1+k_22^{j_2-j_1}.$$ This leads to a contradiction with $k_1$ being odd unless $j_2=j_1=j.$ So $$3\cdot 2^{n-j}=k_1k_2 2^j +k_1+k_2.$$

This leads to $$k_1k_2 < 3\cdot 2^{n-2j}$$ and therefore we conclude that $k_1=k_2=1$ or $n-2j\ge 1.$ The case $k_1=k_2=1$ leads to contradiction because you will end up with $3\cdot 2^{n}=2^{n+1}+2^n=2^{2j}+2^{j+1},$ so $j=1=n,$ but $6+1=7$ is not a square. On the other hand, $n-2j\ge 1$ implies $(k_1+k_2)$ is an odd integer times $2^{-j}:$ $$3\cdot 2^{n-2j}=k_1k_2+(k_1+k_2)2^{-j}.$$

There is a short but not completely elementary proof for even $n$ in Robinson's "A Report on Primes of the Form $k\cdot2^n+1$ and On Factors of Fermat Numbers."

  • 1
    $\begingroup$ When you say $j>1$, don't you mean $j > m + 1$? Then, when you consider the factorization into $ab$, you have that all three of $n, j_1, j_2$ must be greater than $m+1$. Addition: And how do you know $j_1$ is strictly less than $n$? $\endgroup$ May 4 '20 at 10:58
  • 2
    $\begingroup$ Every odd number can be written uniquely in the form $k\cdot 2^j+1$, with $k$ odd and $j>0$ integers. Now we take two numbers $a,b$ so that $ab$ divides a Fermat number, and never use this information again? We only investigate the information $ab=3\cdot 2^n+1$ without any connection to a Fermat number?! In the special example $3\cdot 2^{23}+1=5^2\cdot 1006633$ we can use the above only to detect that if group two factors to be $a$, the remained to be $b$, then $(a-1)$ and $(b-1)$ have the same $2$-order. (Lucas gives us it is $>m+1$.) How to connect this information to Fermat primes?! $\endgroup$
    – dan_fulea
    May 4 '20 at 16:49
  • 1
    $\begingroup$ Ah you're right $m+1,$ thank you. @JeppeStigNielsen We know $j$ is smaller than $n$ otherwise the side with $k_1k_22^{2j}$ will be much bigger than $2^n.$ dan, I couldn't figure out how to use this information. $\endgroup$ May 4 '20 at 22:12
  • $\begingroup$ By the way, I'm not too familiar with the etiquette on stackexchange. Is it ok to post partial work like this as an answer, or is it preferred to not do this? $\endgroup$ May 4 '20 at 22:15
  • $\begingroup$ I do not know about consensus either, but in my opinion, partial answers are OK when they are too long to fit in the comment format, and when it is clearly stated that is just a partial answer. In fact, I have a bounty that I might as well award to you since there is nothing else I can do with it. However, we still do not know if composite $3\cdot 2^n+1$ can divide a Fermat number. $\endgroup$ May 5 '20 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.