IOQM 2023 Apple Mock Four

This is the fourth IOQM Mock test from MOMC. The problems are taken from HMMT 2008 Guts Round and CMIMC 2022. All the credit and authorship of the problems belongs to their respective sources. There are plenty of great problems that I wasn't able to include in the mock. I encourage you to check them out as well.

Now I would discuss an awesome number theory problem from the mock. So if you are planning to attempt the mock, beware of the spoilers ahead.

Problem 23 $\textbf{(CMIMC 2022 Team Round P13)}$ Let $F_n$ denote the $n$th Fibonacci number, with $F_0=0, F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n \geq 2$. There exists a unique two digit prime $p$ such that for all $n$, $p \mid F_{n+100}+F_n$. Find $p$.

Solution: We use the following two well known results regarding Fibonacci numbers:

• $\gcd(F_m,F_n) = F_{\gcd(m,n)}$. Call this fact $\dagger$.
• $p \mid F_{p-1} \iff p \equiv \pm 1 \pmod 5$ and $p \mid F_{p+1} \iff p \equiv \pm 2 \pmod 5$. Call this fact $\star$.

Firstly observe that $n=0 \implies p \mid F_{100}$. Let $F_{f(p)}$ be the minimal fibonacci number $F$ such that $p$ divides $F$. Now $\dagger$ implies that $p$ also divides $F_{f(p)k}$ . Further, fact $\star$ implies that $f(p)$ divides $p-1$ if $p\equiv \pm 1 \pmod 5$ and $p+1$ if $p \equiv \pm2 \pmod 5$.

Now let $F_{f(p)-1} \equiv j \pmod p$. Thus $F_{f(p)+1} \equiv F_{f(p)+2} \equiv j \pmod p$. Then $F_{f(p)+3} \equiv 2j \pmod p$ and so on. Thus $F_{f(p)+n} \equiv j \cdot F_{n} \pmod p$. Thus in order to have $F_{n+100} + F_n \equiv 0 \pmod p$ we must have $F_{n}(j+1) \equiv \pmod p$. As the greatest common divisor of all the fibonacci numbers is $1$, we must have $j \equiv -1 \pmod p$.

Now we begin our search for two digit prime factors of $F_{100}$. Observe that $f(p) \mid 100 \implies f(p) \in \{1,2,4,5,10,20,25,50,100 \}$. Clearly $p < 10$ if $f(p) \in \{1,2,3,4,5 \}$. If $f(p) = 10$ then $F_{10} = 55 \implies p = 11$ (as $5 \mid F_5 = 5$). We require that $F_9 \equiv -1 \pmod {11}$ but $F_9 = 34 \equiv 1 \pmod {11}$. If $f(p) = 20$ then further if $p \equiv \pm 1 \pmod 5$ then we need $f(p) \mid p-1$ and $p < 100$. There are two primes with this property: $p = 41,61$. Some tedious work shows that for $p=41$, both the required properties: $f(41) = 20$ and $F_{19} \equiv -1 \pmod {41}$ hold true.

It is not very hard to show that this is the unique solution. Some calculations$\mod {61}$ show that $F_{19} \equiv 1 \pmod {61}$. Now if $p \equiv \pm 2 \pmod 5$ then we require $20 \mid p+1$ but $p + 1 \not \equiv 0 \pmod 5$, a contradiction! If $f(p) = 25,50,100$, then there doesn't exist a prime $p \equiv \pm 1 \pmod {f(p)}$ such that $p<100$. We are done!

This is the CODS difficulty rating for today's mock: