Sequence with GCD involved

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

w

3 users

TOPICS

No tags match your search

M

No tags match your search

M

Sequence with GCD involved

G H J

Reveal topic tags

greatest common divisor

L

G H BBookmark kLocked kLocked NReply

Source: 2021 Simon Marais, A2

The post below has been deleted. Click to close.

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

mathematics2004

82 posts

mathematics2004

#1 h Nov 2, 2021, 4:35 PM • 1 Y

Y by GeoKing

Define the sequence of integers $a_1, a_2, a_3, \ldots$ by $a_1 = 1$ , and
$a_{n+1} = \left(n+1-\gcd(a_n,n) \right) \times a_n$ for all integers $n \ge 1$ .
Prove that $\frac{a_{n+1}}{a_n}=n$ if and only if $n$ is prime or $n=1$ .
Here $\gcd(s,t)$ denotes the greatest common divisor of $s$ and $t$ .

Z K Y

The post below has been deleted. Click to close.

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

60 posts

#2 h Nov 9, 2021, 2:26 PM • 1 Y

Y by GeoKing

We prove by induction on $n$ that the set of prime divisors of $a_n$ is exactly the set of prime numbers strictly less than $n$ .

The claim is true for $n = 1$ . Suppose that it is true for $n$ and we prove the case of $n + 1$ .

For one inclusion: the factor $(n + 1 - \gcd(a_n, n))$ is at most $n$ , hence the prime divisors of $a_{n + 1}$ are all less than $n + 1$ .
To prove the other inclusion, we have two cases.
If $n$ is not prime, then any prime number less than $n + 1$ is also less than $n$ , thus is already prime divisor of $a_n$ , and hence prime divisor of $a_{n + 1}$ .
If $n$ is prime, then we have $\gcd(a_n, n) = 1$ because all prime divisors of $a_n$ are less than $n$ . Therefore $a_{n + 1} = na_n$ and the claim is clearly true.

We have proved the claim for all $n$ and the original question is a byproduct of our proof.

Z K Y

The post below has been deleted. Click to close.

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

Mathematicsislovely

245 posts

Mathematicsislovely

#3 h Nov 26, 2021, 8:38 PM • 1 Y

Y by GeoKing

The main claim is that:

When $n$ is prime then $\gcd(n,a_n)=1$ ,which in turn shows $a_{p+1}=p a_p$ for all prime $p$
When $n$ is composite then $\gcd(a_n,n)>1$

Proof. For prime $p$ ,
$a_p=\prod_{i=1}^{p-1} (i+1-\gcd(i,a_i))$ Since each factor is less than $p$ so $p\nmid a_p$ .
For the second statement notice that $a_n|a_{n+1}$ which implies $a_m|a_n,\forall m\le n$ .Let $p$ be a prime divisior of $n$ ,(so $p<n$ ).Then $pa_p=a_{p+1}|a_n$ .But this shows $p|\gcd(n,a_n)\implies 1<p\le \gcd(n,a_n)$ . $\square$

So for composite $n$ we have $\frac{a_{n+1}}{a_n}=n+1-\gcd(a_n,n)<n$ .And when $n$ is prime or 1 then, $\frac{a_{n+1}}{a_n}=n$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

199 posts

#4 h May 5, 2025, 5:54 PM

Y by

Let us write down few terms just to build some intuition,
$\begin{tabular}{c|c c c c c c c c c c c c} $a_n$ & $a_1$ & $a_2$ & $a_3$ & $a_4$ & $a_5$ & $a_6$ & $a_7$ & $a_8$ & $a_9$ & $a_{10}$ & $a_{11}$ & $a_{12}$\\\\ \hline\\ $n$ & $1$ & $1$ & $2$ & $2\cdot 3$ & $2\cdot 3^2$ & $2\cdot 3^2\cdot 5$ & $2\cdot 3^2\cdot 5$ &$2\cdot 3^2\cdot 5\cdot 7$ & $2\cdot 3^2\cdot 5\cdot 7^2$ & $2\cdot 3^2 \cdot 5\cdot 7^2$& $2\cdot 3^2 \cdot 5\cdot 7^2$& $2\cdot 3^2 \cdot 5\cdot 7^2\cdot11$\\ \end{tabular}$ Notice that every prime less than $n$ divides $a_n$ for $n\le 12$ at least and more precisely no prime bigger than $N-1$ divides $a_N$ as well. We ask the question, if this holds for any $n$ .

Claim 1. A prime $p$ divides $a_n$ if and only if $p<n$ .
Proof. This simply follows from an inductive argument (base case holds-refer the table). Suppose this property holds for some natural $N$ then we have,
$a_{N+1}=\underbrace{(N+1-\gcd(N, a_N))}_{\text{less than $N+1$}}\times a_N$ By hypothesis it is true that every prime less than $N$ divides $a_N$ and are the only ones. As $N+1-\gcd(N, a_N)< N+1$ , our claim holds!

To finish off we just need to observe that $\gcd(n, a_n)=1$ if and only if $n$ is a prime which is obvious from our claim and we are done. $\square$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a