MathDB

3

Part of 2010 Hong kong National Olympiad

Problems(1)

number theory equality

Source: 2010 HongKong mathematic Olympiad

2/11/2012
Let nn be a positive integer. Let aa be an integer such that gcd⁡(a,n)=1\gcd (a,n)=1. Prove that aϕ(n)−1n=∑i∈R1ai[ain](modn)\frac{a^{\phi (n)}-1}{n}=\sum_{i\in R}\frac{1}{ai}\left[\frac{ai}{n}\right]\pmod{n} where RR is the reduced residue system of nn with each element a positive integer at most nn.
modular arithmeticfloor functionnumber theory proposednumber theory