MathDB

2

Part of 1996 Bosnia and Herzegovina Team Selection Test

Problems(1)

Bosnia and Herzegovina TST 1996 Day 1 Problem 2

Source: Bosnia and Herzegovina Team Selection Test 1996

9/20/2018
a)a) Let mm and nn be positive integers. If m>1m>1 prove that n∣ϕ(mn−1) n \mid \phi(m^n-1) where ϕ\phi is Euler function b)b) Prove that number of elements in sequence 1,2,...,n1,2,...,n (n∈N)(n \in \mathbb{N}), which greatest common divisor with nn is dd, is ϕ(nd)\phi\left(\frac{n}{d}\right)
Eulernumber theoryEulers functiongreatest common divisorfunction