PUMaC 2012 · 数论（B 组） · 第 8 题

PUMaC 2012 — Number Theory (Division B) — Problem 8

[ 8 ] Let p = 2012 and p = 2012 for all n > 1 . Find the largest integer k such that 1 n k p − p is divisible by 2011 . 2012 2011 1

解析

[ 8 ] Let p = 2012 and p = 2012 for all n > 1 . Find the largest integer k such that 1 n k p − p is divisible by 2011 . 2012 2011 Solution: The difference in question is ( ) ( ) p − p p − p p − p 2011 2010 2011 2010 2011 2010 p − p = p (2012) − 1 = p (2012) − 1 . 2012 2011 2011 2011 We note that we can apply the Lifting the Exponent Lemma to the quantity in parentheses because 2011 is prime. The lemma states that if x and y are integers, n is a positive integer, and p is an odd prime such that p | x − y but x and y are not divisible by p , we have n n v ( x − y ) = v ( x − y ) + v ( n ) p p p v ( m ) v ( m )+1 p p where v ( m ) refers the greatest power in which p divides m , i.e. p | m but p 6 | m . p So by this lemma, 3 ( ) p − p p − p 2011 2010 2011 2010 v (2012) − 1 = v (2011) + v ( p − p ) , 2011 2011 2011 2011 2010 m where v ( x ) denotes the largest m such that 2011 divides x . Clearly v (2011) = 1, so 2011 2011 we need to determine v ( p − p ). But we note that this sequence is recursive, with 1 2011 2011 2010 being added at each step. So we just need to find v ( p − p ). 2011 2 1 ( ) 2011 2011 v ( p − p ) = v 2012(2012 − 1 = v (2011) + v (2011) . 2011 2 1 2011 2011 2011 So v ( p − p ) = 2 and we have v ( p − p ) = 2012, so k = 2012 . 2011 2 1 2011 2012 2011 Problem contributed by Wesley Cao. 4