0
$\begingroup$

Let $n$ be an integer and $F_n:=2^{2^n}+1$. $$n=2,3,4:F_n\equiv17\pmod{30}$$

$\mathbf{Result:}\;n>1:F_n\equiv17\pmod{30}$

$\mathbf{Proof:}$ Suppose $F_n - 1\equiv16\pmod{30}$. Then $2^{2^{n+1}}=({2^{2^n}})^2\equiv16^2\pmod{30}\equiv16\pmod{30}$ and $F_{n+1}\equiv17\pmod{30}$.

I found that result using primoradic (see stub OEIS: https://oeis.org/wiki/Primorial_numeral_system).

That's the way I found that result, which I did't know before and I wonder if there are other results with $\;210,\;2310,\;30030,\;\ldots$ (primorials)

P.S. : In primoradic, using Charles-Ange Laisant's notations for factoradic (with $A=10, B=11, C=12, D=13,\ldots$) $$17=(000000.221)$$ $$257=(000011.221)$$ $$65.537=(2.240.221)$$ $$F_5=(J.5F1.721.221)$$ Perhaps, someone could give $F_6$, $F_7$ ...in primoradic, just for fun. Fill in the holes :$$F_6=(........0.221)$$ $$F_7=(......1:1:...)$$ $$F_8=(......4:0:...)$$ $$F_9=(......2:1:...)$$ $$F_{10}=(....0:0:...)$$ $$F_{11}=(......1:...)$$ $$F_{12}=(......0:...)$$ $$F_{13}=(......1:...)$$ $$2^{16384}+1=(......:0:...)$$ I have verified each of these results with my spreadsheet. Maybe $F_n\equiv17\pmod{210}$ if n is even and $47$ if n is odd? A result appears clearly with $2310$ too. We need a proof. Perhaps here :I'm trying to generalize some simple results about $ 2 ^ n $. It's useful to write them in primoradic (see stub OEIS)., will be useful.

$\endgroup$

2 Answers 2

2
$\begingroup$

Primorials play no role. Rather, fixed points of (quadratic) polynomial iterations are key.

Notice $\ \color{#0a0}{F_{n+1} = (F_n-1)^2+1} = F_n^2 -2F_n + 2\ $ hence $\!\bmod 30\!:\ F_{n+1}\equiv F_n\iff 0 \equiv F_n^2-3F_n + 2 \equiv (F_n-1)(F_n-2).\,$ Using CRT to combine the roots $\,F_n\equiv 1,2\,$ mod $\,2,3,5\,$ (as here) yields $\,2^3\,$ roots $\,1,2,7,11,16,\color{#c00}{17},22,26 \pmod{\!30}$.

So, $\!\bmod 30,\,$ any sequence $\,F_n\,$ satisfying said $\rm\color{#0a0}{recurrence}$ remains constant afterwards once it takes the value of one of those roots, e.g. your Fermat numbers, where $\,F_2\equiv \color{#c00}{17}\pmod{\!30}.$

Remark $ $ The same method works to solve for (modular) fixed points of any polynomial iteration, i.e. if the $\,a_i$ satisfy a recurrence $\,a_{n+1} = f(a_n)\,$ for a polynomial $\,f(x),\,$ then $\,a_n\,$ is a fixed point, i.e. $\, a_{n+1} = a_n\iff f(a_n) = a_n\iff a_n\,$ is a root of $f(x)-x,\,$ so finding fixed points of polynomial iterations reduces to finding roots of polynomials.

In your case note that subtracting $1$ from the roots shows they are roots of $\,x^2\equiv x,\,$ i.e. idempotents, so are $\equiv 0$ or $1$ for each prime modulus. Idempotents are well-studied since they play crucial roles in factorization of rings (e.g. they essentially govern the ring factorizations given by CRT = Chinese Remainder Theorem).

$\endgroup$
7
  • $\begingroup$ @Stéphane It's easy $\,\color{#0a0}{F_{n+1}-1 = (F_n-1)^2}\,$ means $\,2^{\large 2^{\Large n+1}}\!\! = (2^{\large 2^{\Large n}})^{\large 2},\, $ true by exponent laws. $\ \ $ $\endgroup$ May 9, 2021 at 10:49
  • $\begingroup$ @Stéphane Notice my location is "Shoulders of Giants". Luckily, the recursion is well-founded (on Gauss, Dedekind, Noether, Krull, etc). $\endgroup$ May 9, 2021 at 11:01
  • $\begingroup$ Plus by $F_n=2M_{M_n}+3$ it's equivalent to $M_{M_n}\equiv 7 \pmod {30}$ $\endgroup$ May 9, 2021 at 11:22
  • $\begingroup$ Of course it does take a little bit of work to derive the formula $F_n=2^{2^n}+1$ from $F_n=F_1F_2\cdots F_{n-1}+2$, the basic definition of the Fermat numbers. $\endgroup$
    – bof
    May 9, 2021 at 12:02
  • 3
    $\begingroup$ @bof Did you miswrite, or do you really mean to claim that $\,F_n=F_1F_2\cdots F_{n-1}+2\,$ is the "basic definition" of the Fermat numbers? $\endgroup$ May 9, 2021 at 12:15
2
$\begingroup$

Of course $$F_n=F_0F_1\cdots F_{n-1}+2\equiv2\pmod{F_0F_1}$$ for $n\gt1$, and $F_n$ is odd, so there you have it.

Likewise, $F_n\equiv2\pmod{17}$ for $n\gt2$, $F_n\equiv2\pmod{257}$ for $n\gt3$, etc. This is why the Fermat numbers are pairwise relatively prime.

$\endgroup$
2
  • 1
    $\begingroup$ But that formula is so specific to Fermat numbers that it doesn't generalize to other recurrences, whereas the fixed-point view does, which is why I chose that much more general view in my answer. $\endgroup$ May 9, 2021 at 8:15
  • $\begingroup$ No need to apologize - this method is nice and well worth mention. The point of my comment was merely to spark readers to think about the generality of various approaches. $\endgroup$ May 9, 2021 at 10:09

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.