Gcd of some consecutive terms of a recursive sequence

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Gcd of some consecutive terms of a recursive sequence

G H J

Reveal topic tags

greatest common divisor

L

G H BBookmark kLocked kLocked NReply

Source: Swiss MO 2023/3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1184 posts

L567

#1 h Mar 12, 2023, 11:56 AM

Y by

Let $x,y$ and $a_0, a_1, a_2, \cdots$ be integers satisfying $a_0 = a_1 = 0$ , and $a_{n+2} = xa_{n+1}+ya_n+1$ for all integers $n \geq 0$ . Let $p$ be any prime number. Show that $\gcd(a_p,a_{p+1})$ is either equal to $1$ or greater than $\sqrt{p}$ .

This post has been edited 3 times. Last edited by L567, Mar 12, 2023, 12:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

277 posts

#2 h Mar 12, 2023, 12:16 PM • 3 Y

Y by VicKmath7, GuvercinciHoca, ken3k06

Outline from Contest:
Very standard idea, you can do similar things for Pisano period for Fibonacci, let $q$ be a prime.

If $q$ is a divisor of $y$ then $q \nmid gcd(a_n,a_{n+1})$ for $n \geq 1$ is easy to see.

If $gcd(q,y) = 1$ , then take by pigeonhole some pair of pairs $(a_i,a_{i+1}) = (a_j,a_{j+1})$ in $\mathbb{F}_q^2$ and $i \neq j$ , $i,j \leq q^2$ , then notice that in $\mathbb{F}_q^2$ $ya_{i-1} \equiv a_{i+1}-xa_i-1 = a_{j+1}-xa_j-1 = ya_{j-1}$ which means that $(a_{i-1},a_i) = (a_{j-1},a_j)$ in $\mathbb{F}_q^2$ as well, then take $(i,j)$ to be such that $i$ is minimal and notice that this forces $i = 0$ and take $j \leq q^2$ to be minimal such that $(0,0) = (a_j,a_{j+1})$ , then it is easy to see that $j = q_i$ is the minimal period of this sequence, that is, $(0,0) = (a_p,a_{p+1})$ means that $q_i \mid p$ , as $q_i \neq 1$ , we get $q^2 \geq q_i = p$ , then as $q^2 \neq p$ , we get $q > \sqrt{p}$ for all prime divisors of $gcd(a_p,a_{p+1})$ which finishes.
Remark:
Problems are ordered by difficulty (mod 4), only $5$ of the problems were released due to confidentiality.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

128 posts

#3 h Dec 30, 2023, 10:05 PM

Y by

We uploaded our solution https://calimath.org/pdf/SwissMO2023-3.pdf on youtube https://youtu.be/AzB3Q0aSshU.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a