Divisibilità e non....

[Ani-sama]

Dimostrare che:

1) $ ${3^{n+1}} | {2^{3^n} +1}, \quad n \in \mathbb{N}_0$ $

2) $ ${2^{2^{n}}} \not\vert {3^{2^n} - 1}, \quad n \in \mathbb{N}, \quad n>2$ $

[darkcrystal]

1) Calcoliamo innanzitutto $ \phi(3^{n+1})=3^{n+1}-3^n=3^n(3-1)=2*3^n $
L'ordine moltiplicativo modulo $ 3^{n+1} $ divide la phi, ma non può essere dispari, in quanto si avrebbe
$ 2^d \equiv 1 \pmod {3^{n+1}} $; a maggior ragione questa deve valere modulo 3, $ (-1)^d \equiv 1 \pmod 3 $ che è assurdo. Perciò l'ordine moltiplicativo è pari, ma è noto che elevando la base alla metà dell'ordine moltiplicativo si ottiene un valore congruo a -1.
Sia k l'ordine moltiplicativo.
k è del tipo $ 2*3^a $, da cui la relazione iniziale diventa $ 2^{\frac{k}{2}*d}+1 \equiv -1 +1 \equiv 0 \pmod {3^{n+1}} $

[enomis_costa88]

Dimostrare che:

1) $ ${3^{n+1}} | {2^{3^n} +1}, \quad n \in \mathbb{N}_0$ $

$ 2^{3^n}+1=3 \prod_{i=0}^{n-1}(2^{2(3)^i}+1-2^{3^i}) $
inoltre:
Le potenze pari di due sono congrue ad uno modulo 3.
Le potenze dispari di due sono congrue a 2 modulo 3.
Quindi:
$ 2^{2(3)^i}+1-2^{3^i} \equiv 0 \pmod 3 $ per qualsiasi i.
$ {3^{n+1}} | $ il prodotto di n+1 termini multipli di 3 (e diversi da 0).

2) $ ${2^{2^{n}}} \not\vert {3^{2^n} - 1}, \quad n \in \mathbb{N}, n>0$ $

$ {3^{2^n} - 1} = 2*4\prod_{i=1}^{n-1}(3^{2^i}+1) $
inoltre se k=2t:
$ 3^k \equiv 9^t \equiv 1^t \equiv 1\pmod 8 $;
quindi:
$ 9^t+1\equiv 2 \pmod 8 $
la massima potenza di due che divide un numero congruo a 2 modulo 8 è 2.
quindi il numero di fattori 2 presenti in $ 2*4\prod_{i=1}^{n-1}(3^{2^i}+1) $ è:
$ (n-1)+2+1=n+2 \leq 2^n-1 $ per n > 2.

[Ani-sama]

2) $ ${2^{2^{n}}} \not\vert {3^{2^n} - 1}, \quad n \in \mathbb{N}, n>0$ $

$ {3^{2^n} - 1} = 2*4\prod_{i=1}^{n-1}(3^{2^i}+1) $
inoltre se k=2t:
$ 3^k \equiv 9^t \equiv 1^t \equiv 1\pmod 8 $;
quindi il massimo numero di fattori 2 presenti in $ 2*4\prod_{i=1}^{n-1}(3^{2^i}+1) $ è $ n-1+2+1=n+2 \leq 2^n $ per n > 1.
Inoltre n=1 è un controesempio alla tesi che risulta quindi invalidata

Uhm... è invalidata anche per $ $n=2$ $... infatti mi sono sbagliato a mettere la limitazione, che è invece $ $n>2$ $

Comunque vengono bene anche con una banale induzione...

[enomis_costa88]

$ n+2 \leq 2^n $

Quì ci andava il minore stretto infatti che vale per n>2 metto a posto subito