Matematické Fórum

liamlim

Zdravím. Vymyslel jsem příklad, kde si můžete vyzkoušet základní práci v modulární aritmetice.

Buď dáno $n\ge 2$ přirozené. Dále buďte $x_1, x_2, \cdots, x_{n^2}$ přirozená čísla nesoudělná s $n$ .

Dokažte, že:
$\left(\prod_{i=1}^{n^2}x_i\right)^{\varphi(n)}\equiv 1 + \left(\sum_{i=1}^{n^2}x_i^{\varphi(n)}\right)\mod n^2$

pozn.: jako $\varphi(n)$ značím eulerovu funkci čísla $n$

edit.: nápověda: zkuste nejprve dokázat (a poté využít) následující: $(xy)^{\varphi(n)} + 1 \equiv x^{\varphi(n)} + y^{\varphi(n)}\mod n^2$