Notevolissime proprietà dell'ordine moltiplicativo

[HiTLeuLeR]

Wow... Sentite cosa mi sono inventato ieri pomeriggio: non vi nascondo che ne vado particolarmente fiero, e non tanto per la dimostrazione, quanto piuttosto per l'idea in sé...

Problema #1: per ogni $ n \in\mathbb{N}_0 $, sia $ \mathcal{T}(n) := \{a\in\mathbb{N}_0: a \leq n\mbox{ }\wedge\mbox{ }\gcd(a,n) = 1\} $ l'insieme dei totativi di $ n $. Calcolare il resto $ r_n $ della divisione intera per $ n $ della sommatoria $ \displaystyle{\sum_{a\in \mathcal{T}_n} a^{\mbox{ord}_n(a) - 1}} $, estesa quest'ultima a tutti e soli gli elementi di $ \mathcal{T}_n $. Qui come al solito, $ \mbox{ord}_n(a) $ denota l'ordine moltiplicativo di $ n $ alla base $ a $.

NOTA: se proprio non sapete di cosa si stia parlando, potrebbe esservi utile dare una cliccatina proprio qui.

[ma_go]

$ 0 $? (escluso il caso $ n = 2 $, che è patologico)
se ho interpretato bene, non mi sembra neppure difficile... poi magari mi sbaglio, però...

[HiTLeuLeR]

Sì, ma_go, the answer is right. Confermo anche la tua impressione: la soluzione è quasi banale. Eppure il meglio deve ancora venire... Aspetta e vedrai, uomo di poca fede! Adesso le prove, su...

[ma_go]

ok..
piccolo lemmino: $ \{ x| (x,n) = 1, x \le n \} = \{ x | x = a^{-1} (\bmod n), (a,n) = 1\} $.
ovvero, per ogni numero primo con $ n $ esiste ed è unico l'inverso $ \bmod n $.
ora, la somma di euler, è la somma degl inversi $ \bmod n $, presa su tutti i numeri primi con $ n $. per il lemma, essa è pari alla somma di tutti i numeri che non sono primi con $ n $, che quindi è $ 0 (\bmod n) $.
(divertitevi a dimostrarlo, non è del tutto banale, ma neppure difficile).

[HiTLeuLeR]

Ok, promosso con riserva: alcuni dettagli in più, oltre al fatto che sarebbero risultati particolarmente graditi al sottoscritto, pure avrebbero giovato (non v'è dubbio) a quest'adorabile comunità...

Problema #2: per ogni intero $ n > 0 $ ed ogni $ s \in \mathbb{N} $, calcolare $ r_n^{(s)} := \displaystyle{\sum_{a=1}^{2^{n-1}} (2k-1)^s} \bmod 2^n $.

...ma non finisce certo qui!!! Suvvia, vi prego, dimostratemi che tutto questo è banale routine...