Divisibilità

[Pachisi]

Dimostrare che $2^147-1$ è divisibile per $343$

[dan952]

Una soluzione didattica con il teorema di Eulero...

$343=7^3$ quindi $\phi(7^3)=7^3-7^2=294=2 \cdot 147$...

[robbstark1]

Propongo invece una soluzione operaia per gli ignoranti come me, che non conoscevano nè il teorema di Eulero nè la sua funzione.

Notiamo che $147 = 3*7^2$, possiamo quindi scomporre come differenza tra 49-esime potenze:
$2^{147} - 1 = (2^3 - 1)(2^{144} + 2^{141} + 2^{138} + ... + 1) = 7*(2^{144} + 2^{141} + 2^{138} + ... + 1)$
Concentriamoci ora sul secondo fattore.
Notiamo che è la somma di 49 potenze di $2$. Se le raggruppiamo a gruppi di 7, a partire dalle 7 più piccole, poi le seconde, e cosí via, otteniamo:
$2^{144} + 2^{141} + 2^{138} + ... + 1 = (1+2^3+2^6+2^9+2^{12}+2^{15} + 2^{18})(1+2^{21}+2^{42}+2^{63}+2^{84} + 2^{105} + 2^{126})$
Ora è facile dimostrare che $2^{3n} \equiv 1 mod 7$, quindi ciascuno dei due fattori è multiplo di $7$, in quanto somma di 7 termini con resto $1$.
Abbiamo dunque scomposto $2^{147} - 1$ come prodotto di 3 termini multipli di $7$.

[dan952]

Mi sono accorto che manca un pezzo:

Da Eulero deduciamo che $2^{147} -= +- 1 mod 343$ tuttavia $2^{147}=1mod7$ e poiché $(2^{147}+1,2^{147}-1)$ non può essere divisibile per 7 segue la tesi

[Pachisi]

Ok