# How do we use the hint to show the divisibility?

I want to show that if $$m=n^{13}-n$$ and $$n>1$$ then $$30290 \mid F_m$$. (Hint: Show first that $$a^{13} \equiv a \mod{2730}$$.)

$$F_m$$ is the $$m$$-th Fibonacci number.

I have shown the hint as follows:

$$2730=2 \cdot 3 \cdot 5 \cdot 7 \cdot 13$$.

Using Fermat's little theorem, we deduce that $$a^{13}\equiv a \pmod{5}$$, $$a^{13}\equiv a \pmod{2}$$, $$a^{13}\equiv a \pmod{3}$$, $$a^{13}\equiv a \pmod{7}$$ and $$a^{13}\equiv a \pmod{13}$$.

Since $$2,3,6,7,13$$ are all relatively prime, we deduce that $$2730 \mid a^{13}-a$$.

But how can we use the fact that $$a^{13} \equiv a \mod{2730}$$ in order to deduce that $$30290 \mid F_m$$ ?

Let's look at the first few Fibonacci numbers. In particular $$F_2$$, $$F_3$$, $$F_5$$, $$F_7$$, and $$F_{13}$$. The sequence is $$1,\mathbf{1},\mathbf{2},3,\mathbf{5},8,\mathbf{13},21,34,55,89,144,\mathbf{233}.$$ We can ignore $$F_2=1$$, but $$F_3=2$$, $$F_5=5$$, $$F_7=13$$, and $$F_{13}=233$$ are all distinct primes, and their lcm is therefore the product $$2\cdot 5\cdot 13\cdot 233=30290$$.

Finally we link this fact with the part that you have shown by noting that if $$n\mid m$$, then $$F_n\mid F_m$$.

Proof of the fact:

The Fibonacci sequence is also given by the following formula: $$\newcommand\bmat{\begin{pmatrix}}\newcommand\emat{\end{pmatrix}} \bmat F_{n+1}\\F_n\emat=\bmat 1&1\\1&0 \emat^n\bmat 1\\ 0\emat.$$ Now suppose for contradiction that $$F_n\nmid F_m$$ for some integers $$n$$ and $$m$$ with $$n\mid m$$. Then let $$k$$ be the least positive integer such that $$F_n\nmid F_{kn}$$. Then we have that $$\bmat F_{kn+1}\\F_{kn}\emat =\bmat 1&1\\1&0 \emat^{kn}\bmat 1\\ 0\emat =\bmat 1&1\\1&0 \emat^{(k-1)n}\bmat 1&1\\1&0 \emat^{n}\bmat 1\\ 0\emat =\bmat 1&1\\1&0 \emat^{(k-1)n}\bmat F_{n+1} \\ F_n \emat.$$ Taking this equation mod $$F_n$$, we see that $$\bmat F_{kn+1}\\F_{kn}\emat =\bmat 1&1\\1&0 \emat^{(k-1)n}\bmat F_{n+1} \\ 0 \emat =F_{n+1} \bmat 1&1\\1&0 \emat^{(k-1)n}\bmat 1 \\ 0 \emat =F_{n+1} \bmat F_{(k-1)n+1} \\ F_{(k-1)n} \emat,$$ so mod $$F_n$$, we have $$F_{kn}=F_{n+1}F_{(k-1)n}$$, but by assumption $$k$$ was the least positive integer such that $$F_n\nmid F_{kn}$$, so $$F_n\mid F_{(k-1)n}$$ contradiction.

• I see... But I haven't understood how we deduce that $F_{2730}=30290$... Could you explain it to me? – Evinda Nov 5 '18 at 21:17
• @Evinda, Ah sorry, we don't deduce that $F_{2730}=30290$, instead, use that $3,5,7,13 \mid m$ to conclude $F_3,F_5,F_7,F_{13}\mid F_m$. Then their lcm divides $F_m$. – jgon Nov 5 '18 at 21:18
• But we have $30290=2 \cdot 5 \cdot 13 \cdot 233$. And $233$ does not divide $2730$. So how do we deduce this? – Evinda Nov 5 '18 at 21:29
• @Evinda Yes, but try reading my last comment again. I'm not sure why you're asking what you're asking. I'm not saying that 233 divides 2730. I'm saying 13 divides 2730, therefore 233 divides $F_{2730}$. – jgon Nov 5 '18 at 21:31
• @Evinda Further, the fact that the $F_i$ are pair coprime follows immediately from the fact that their indices are pair-coprime - see my answer. Also I link there to a generalization of the Euler Fermat theorem that immediately yields the claimed factors of $n^{13}-n.\,$ These more general viewpoints often come in handy. – Bill Dubuque Nov 5 '18 at 22:02

$$F_i$$ obey $$\, j\mid k\,\color{#c00}{\overset{\rm D}\Rightarrow}\, F_j\mid F_k,\,$$ and $$\,\gcd(F_j,F_k) = F_{\gcd(j,k)},\,$$ being a strong divisibility sequence

By here $$\ 3,\ 5,\ 7,\ 13\ \mid n^{13}-n\$$ for all integers $$n,\,$$ by $$\, \ 2,4,6,12\mid 13\!-\!1$$

$$\ \, \color{#c00}{\overset{\rm D}\Rightarrow}\ F_3,F_5,F_7,F_{13}\mid F_{\large n^{13}-n}\$$ for all integers $$n$$

So their lcm = product $$= 2\cdot 5\cdot 13\cdot 233 = 30290$$ also divides $$F_{\large n^{13}-n}\,$$ since $$F_i$$ with coprime indices are coprime by the above gcd formula.  QED