PUMaC 2015 · 团队赛 · 第 6 题

PUMaC 2015 — Team Round — Problem 6

[ 4 ] What is the smallest positive integer n such that 2 − 1 is a multiple of 2015?

解析

[ 4 ] What is the smallest positive integer n such that 2 − 1 is a multiple of 2015? n n Solution: This implies that 2 is 1 modulo 5, 13, and 31. Clearly, 2 ≡ 1 (mod 31) if and 12 only if n is a multiple of 5. We know that 2 ≡ 1 (mod 13) by Fermat’s Little Theorem, and 6 4 n neither 2 nor 2 are 1 (mod 13), so 2 ≡ 1 (mod 13) if and only if n is a multiple of 12. We n know that for any n that is a multiple of 4 (and thus also any multiple of 12), 2 ≡ 1 (mod 5), so we conclude that the smallest n is the smallest positive integer divisible by 5 and 12, which is 60 . Author: Eric Neyman