Brucialato

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Brucialato

Messaggio da Talete »

Siano $a$ e $n$ interi positivi. Mostrare che
\[\sum_{i=1}^n a^{(i,n)}\]
è multiplo di $n$; dove $(i,n)$ è il massimo comun divisore tra $i$ ed $n$.
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Salvador
Messaggi: 42
Iscritto il: 09 apr 2017, 14:35

Re: Brucialato

Messaggio da Salvador »

Testo nascosto:
Sia $f(a,n) = \sum_{i=1}^{n}{a^{(i,n)}}$.

Chiaramente $(i,n)$ è un divisore di $n$. Se $d | n$, vi sono $\phi(\frac{n}{d})$ interi compresi fra 1 ed $n$ il cui GCD con $n$ è esattamente $d$ : infatti questi sono esattamente quanti i numeri compresi fra $1$ ed $\frac{n}{d}$ coprimi con $\frac{n}{d}$, ovvero $\phi(\frac{n}{d})$. Per ognuno di questi si ha $a^(i,n) = a^d$, pertanto:
$$f(a,n) = \sum_{d | n}{\phi(\frac{n}{d})a^d} = \sum_{d | n}{\phi(d)a^{\frac{n}{d}}}$$

Dimostriamo ora per induzione che se $n=p^k$, con $p$ primo e $k \geq 1$ la tesi è vera.
Per $k=1$ si ha $f(a,p)=\phi(1)a^p + \phi(p-1)a = a^p+(p-1)a \equiv a^p - a \equiv 0 \pmod{p}$.

Supponiamo ora la tesi vera per $p^{k-1}$. Abbiamo:
$f(a,p^k) = \phi(1)a^{p^k} + \phi(p)a^{p^{k-1}} + ... + \phi(p^k)a \equiv a^{p^{k-1}} + (p-1)a^{p^{k-1}} + ... + \sum_{i=2}^{k}{\phi(p^i)a^{p^{k-i}}} \equiv pa^{p^{k-1}} + \sum_{i=2}^{k}{p^{i-1}(p-1)a^{p^{k-i}}} \equiv p f(a,p^{k-1}) \equiv 0 \pmod{p^k}$,
poiché per ipotesi induttiva $f(a,p^{k-1}) \equiv 0 \pmod{p^{k-1}}$.

Adesso consideriamo $n$ qualsiasi e sia $p$ un primo che divide $n$ e $k=v_p(n)$.

Osserviamo ora che per ogni divisore $d$ di $\frac{n}{p^k}$, $dp^i, 0 \leq i \leq k$ è un divisore di $n$ e per ogni divisore $b$ di $n$ con $0 \leq v_p(b) \leq k$, $\frac{b}{p^v_p(b)}$ è un divisore di $\frac{n}{p^k}$: pertanto possiamo raggruppare i divisori di $n$ in $\sigma\left(\frac{n}{p^k}\right)$ insiemi, in modo che per ogni divisore $d$ di $\frac{n}{p^k}$ esista esattamente un insieme che contiene tutti i divisori di $n$ della forma $dp^i, 0 \leq i \leq k$.

Usiamo quindi ciò per riscrivere $f$ come:

$f(a,n) = \sum_{d | \frac{n}{p^k}}{\phi(d) \left( \sum_{i=0}^{k}{\phi(p^i)(a^{\frac{n}{dp^k}})^{p^{k-i}}}\right) } = \sum_{d | \frac{n}{p^k}}{\phi(d) f(a^{\frac{n}{dp^k}},p^k)} \equiv 0 \pmod{p^k}$,

dove l'ultima congruenza si ha per quanto dimostrato sopra. Poiché ciò vale per ogni primo $p$ che divide $n$, si ha $f(a,n) \equiv 0 \pmod{n}$.
Talete
Messaggi: 745
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Brucialato

Messaggio da Talete »

Testo nascosto:
Io ho usato Burnside (Lasker triggered), da cui poi il nome del topic.
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo
Rispondi