返回题库

PUMaC 2013 · 数论（B 组） · 第 6 题

PUMaC 2013 — Number Theory (Division B) — Problem 6

专题
Discrete Math / 离散数学
难度
L3
来源
PUMaC

题目详情

  1. [ 6 ] Let d be the greatest common divisor of 2 − 2 and 2 − 2. Find the remainder when d is divided by 2013.
解析
  1. [ 6 ] Let d be the greatest common divisor of 2 − 2 and 2 − 2. Find the remainder when d is divided by 2013. Solution We have 10 45 10 45 (10 , 45) 5 30 30 (30 − 1 , 30 − 1) 30 − 1 30 d = (2 − 2 , 2 − 2) = 2 · (2 − 1) = 2 · (2 − 1) = 2 − 2 . 5 As φ (2013) = 1200 and 1200 | 30 , the remainder is 2012.