Let $p$ be a fixed prime number. We consider four integers $a, b, c, d \in \mathbb{Z}$ and a sequence $\left(x_{n}\right)$ such that:

$$
\left\{\begin{array}{l}
x_{0}=c \\
x_{1}=d \\
x_{n+2}=a x_{n+1}+b x_{n} \quad n \geq 0
\end{array}\right.
$$

Let $t_{p}$ be the smallest integer such that $x_{n+t_{p}} \equiv x_{n}(\bmod p)$ for all $n \geq p^{2}$ (we set $t_{p}=+\infty$ if such an integer does not exist). What is the largest possible value of $t_{p}$?

## Solutions found by students
(solved by Elias Caeiro)

We are in $\mathbb{F}_{p^{2}}$, the set of roots of quadratic polynomials with coefficients in $\mathbb{F}_{p}$: if $P \in \mathbb{F}_{p}[X]$ is irreducible of degree 2, $\mathbb{F}[X] /\langle P\rangle$ is a field of cardinality $p^{2}$ and $P$ has a root $(X)$ there. By the uniqueness (up to isomorphism) of the field with $p^{2}$ elements, it can be identified with $\mathbb{F}_{p^{2}}$. For degree 1, this is obvious.

If $X^{2}-a X-b$ has a double root, $x_{n}=P(n) \alpha^{2}$ with $\alpha$ the double root and $P \in \mathbb{F}_{p}[X]$ of degree 1. The period then divides $p(p-1)$ and in particular $t_{p} \leqslant p^{2}-1$.

If $X^{2}-a X-b$ has two distinct roots $\alpha$ and $\beta$, then $x_{n}=\mu \alpha^{n}+\nu \beta^{n}$ with $\mu, \nu \in \mathbb{F}_{p^{2}}^{*}$. By Lagrange's theorem (in $\left(\mathbb{F}_{p^{2}}, \cdot\right)$ of cardinality $\left.p^{2}-1\right)$, the period divides $\left.p^{2}-1\right)$.

Finally, let's show that the period can be $p^{2}-1$ (which will be the maximum).

Since $\left(\mathbb{F}_{p^{2}}^{*}, \cdot\right)$ is cyclic, there exists an element $\alpha$ of order $p^{2}-1$. But since the order of $\alpha$ does not divide $p-1, \alpha \notin \mathbb{F}_{p}$. We set $x_{n}=\alpha^{n}+\bar{\alpha}^{n}$ where $\bar{\alpha}$ is the conjugate of $\alpha$ (the other root of its minimal polynomial in $\left.\mathbb{F}_{p}[X]\right)$. This is indeed a linear recurrence sequence of order 2 with period $t$ dividing $p^{2}-1$.

We have $\alpha^{t}+\bar{\alpha}^{t}=2, \alpha^{t+1}+\bar{\alpha}^{t+1}=\alpha+\bar{\alpha}$. Since $\left|\begin{array}{ll}1 & 1 \\ \alpha & \bar{\alpha}\end{array}\right|=\alpha-\bar{\alpha} \neq 0$, there exists a unique solution to the system

$$
\left\{\begin{array}{l}
x+y=2 \\
\alpha x+\bar{\alpha} y=\alpha+\bar{\alpha}
\end{array}\right.
$$

Thus $x=\alpha^{t}=1$ and $y=\bar{\alpha}^{t}=1$. But $\alpha$ is of order $p^{2}-1$ so $p^{2}-1|t| p^{2}-1$, which concludes: $t=p^{2}-1$.

## X. Memorable Quotes

- Martin: "So to do this... I propose we change the statement."
- Rémi: "The definition of functional equations is to tinker."
- Aline: "We should start a club of students to whom I've given false exercises..."
- Aline: "You shouldn't try to be smarter than the one who created the exercise."
- Paul, during class: pretends to be an airplane
- Théo, on an exercise about Parisians: "So there are 600,000 cases." A student: "600,001 if you count the bald ones." Théo: "Thanks, Mathieu Barré."
- Tristan, as a helicopter passes by: "There's a difference between saving lives and circling around my classroom."
- Mathieu comes to talk to a group of students, then leaves

Lise: "Oh. I thought he was going to tell us something interesting."

![](https://cdn.mathpix.com/cropped/2024_05_10_00138f973c2e12c014a0g-457.jpg?height=63&width=1671&top_left_y=1462&top_left_x=221)
Why go to Castorama to do so much DIY?

- Justin, on the same exercise: "I'm pretty convinced that I won't be convinced."
- Martin tries to motivate Hannah: "So, what do you think of this exercise?" Hannah: "Well, it seems true."
- Paul: "Your challenge is not to do math, but to speak louder than Auguste."
- Paul: "Let me think that I'm useful for something."

- Théo: "Strange. When it comes to understanding math, you can do it, but when it comes to understanding my jokes, I only see two people forcing themselves to laugh."

- Tristan, when the tex successfully compiled: "Long live life."

[^0]:    1. Turn off the light if it is on, turn it on otherwise.
[^1]:    5. Whether they make sense or not, they mostly don't make sense in reality.