PUMaC 2021 · 数论（A 组） · 第 8 题

PUMaC 2021 — Number Theory (Division A) — Problem 8

Consider the sequence given by a = 3 and such that for i ≥ 1, we have a = 2 + 1. Let 0 i 3 ′ 3 m be the smallest integer such that a divides a . Let m the smallest integer such that a m 3 m ′ ′ divides a . Find the value of m . m 1

解析

Consider the sequence given by a = 3 and such that for i ≥ 1, we have a = 2 + 1. Let 0 i 3 ′ 3 m be the smallest integer such that a divides a . Let m the smallest integer such that a m 3 m ′ ′ divides a . Find the value of m . m Proposed by: Frank Lu Answer: 35 First, we show that a divides a for each nonnegative integer 1 . We do this by induction. i i +1 Our base case is i = 0 , by which we see that this holds trivially. Now, say that a divides i a i +1 a i a i +1 a i a . Then, notice that a = 2 + 1 = 2 + 1 . Notice that each of our a will be odd, i +1 i +2 i a a i +1 i +1 a a i a a i i i meaning that we see that a = (2 ) + 1 is going to be divisible by 2 + 1 = a . i +2 i +1 This finishes our induction. Now, given a prime p, let i ( p ) be the smallest index i so that a is i ( p ) divisible by p. We claim that v ( a ) , v ( a ) , v ( a ) , . . . is an arithmetic progression. p p p i ( p ) − 1 i ( p ) i ( p )+1 To prove this, we again show with induction that v ( a ) = ( k + 1) v ( a ) . Our base case p p i ( p )+ k i ( p ) is k = 0 , with k = − 1 given. From here, given this for all values before i ( p ) + k, notice that, a i ( p )+ k a i ( p )+ k − 1 a a i ( p )+ k i ( p )+ k − 1 by the lifting the exponent lemma, we have that v (2 + 1) = v (2 + p p a a i ( p )+ k i ( p )+ k a a a i ( p )+ k a i ( p )+ k − 1 i ( p )+ k − 1 i ( p )+ k − 1