Problema: stabilire condizioni necessarie e sufficienti sull'intero $ n \geq 0 $ affinché $ 101 \mid (1^n + 2^n + \ldots + 100^n) $.
Liberamente ispirato ad un problema dell'edizione 1901 dell'Eotvos Competition.
Quando 101 | (1^n + 2^n + ... + 100^n)
- psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
L'ora è tarda e io ho sonno per cui il rischio di essere cerberizzato da hit è molto elevato. Anyway:
Se $ n=0 $ allora $ \displaystyle\sum_{i=1}^{100}i^n=\sum_{i=1}^{100}i^0=100 $ quindi $ n=0 $ non va bene.
Per continuare osserviamo che 101 è un numero primo, dunque esiste un elemento $ g $ generatore di tutte le classi di congruenza modulo 101.
Allora possiamo scrivere:
$ \displaystyle\sum_{i=1}^{100}i^n\equiv\sum_{i=1}^{100}(g^{i})^{n} $$ \displaystyle\equiv\sum_{i=1}^{100}(g^{n})^{i}\equiv\frac{1-(g^{n})^{101}}{1-g^n}-1 $$ \displaystyle\equiv\frac{1-(g^{101})^{n}}{1-g^n}-1\equiv\frac{1-g^{n}}{1-g^n}-1\equiv1-1\equiv0\ \ \ \ \ \ (101) $
Quindi ogni numero naturale non zero va bene.
Spero di non aver cannato troppo...
Se $ n=0 $ allora $ \displaystyle\sum_{i=1}^{100}i^n=\sum_{i=1}^{100}i^0=100 $ quindi $ n=0 $ non va bene.
Per continuare osserviamo che 101 è un numero primo, dunque esiste un elemento $ g $ generatore di tutte le classi di congruenza modulo 101.
Allora possiamo scrivere:
$ \displaystyle\sum_{i=1}^{100}i^n\equiv\sum_{i=1}^{100}(g^{i})^{n} $$ \displaystyle\equiv\sum_{i=1}^{100}(g^{n})^{i}\equiv\frac{1-(g^{n})^{101}}{1-g^n}-1 $$ \displaystyle\equiv\frac{1-(g^{101})^{n}}{1-g^n}-1\equiv\frac{1-g^{n}}{1-g^n}-1\equiv1-1\equiv0\ \ \ \ \ \ (101) $
Quindi ogni numero naturale non zero va bene.
Spero di non aver cannato troppo...
Sì, Psion, esattamente! Solo ci aggiungerei (per quanto tu mi obietterai essere implicito) che le riduzioni modulo $ 101 $ da te operate sono valide fintanto che $ g^n \not\equiv 1 \bmod 101 $, il che accade sse $ n \not\equiv 0 \bmod 100 $, siccome $ g $ (per costruzione) rappresenta una radice primitiva modulo $ 101 $. Inoltre...
...ogni numero naturale che non sia zero modulo $ 100 $, altrimenti non ci si capisce una cippa...psion_metacreativo ha scritto:[...] Quindi ogni numero naturale non zero va bene.
- psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00