IOQM 2023 Apple Mock Four

14 July 20233 minutesviews

This article contains spoilers for the mock test.

I recommend attempting the problems before proceeding to read the article. You can download the problems and the answer key using the buttons below.

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 (CMIMC 2022 Team Round P13)\textbf{(CMIMC 2022 Team Round P13)} Let FnF_n denote the nnth Fibonacci number, with F0=0,F1=1F_0=0, F_1=1 and Fn=Fn1+Fn2F_n=F_{n-1}+F_{n-2} for n2n \geq 2. There exists a unique two digit prime pp such that for all nn, pFn+100+Fnp \mid F_{n+100}+F_n. Find pp.

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

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

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

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

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

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