Dimostrare che esiste un intero positico $ $k $tale che per ogni intero positivo $ $n $,
$ $k \cdot 2^n + 1 $ non è primo
k * 2^n + 1 non primo
k * 2^n + 1 non primo
Appassionatamente BTA 197!
-
darkcrystal
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Soluzione vergognosamente brutta, ma trovata in dieci minuti e funge (credo 
)
Voglio dimostrarlo facendo i casi dei residui di n modulo 24.
Scopro che $ 2^{24}-1=3^2 \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 241 $.
Se prendo $ k \equiv 1 \pmod 3 $, allora $ k 2^{dispari} + 1 \equiv 2^{dispari} + 1 \equiv 2+1 \equiv 0 \pmod 3 $. E ciò ci leva tutti gli n dispari.
Prendo poi $ k \equiv 1 \pmod 5 $. Allora se $ n \equiv 2 \pmod 4 $ per lo stesso motivo di prima $ 5|2^n+1 $.
Ciò copre i residui dispari + 2,6,10,14,18,22
E avanti così a coprire residui! Via con $ k \equiv -1 \pmod {13} $, che copre 0 e 12 (perchè $ 2^{12k} \equiv 1 \pmod {13} $)
Con $ k \equiv 3 \pmod 7 $ copro $ n \equiv 4 \pmod 6 $
Avanzano solo 8 e 20 come residui, e 2 primi (17, 241). Dato che, modulo questi primi, 2 ha ordine che divide 24, posso aggiustarmi k in modo che se n è congruo a uno dei 2 residui mancanti modulo 24, allora il tutto è congruo a 0 modulo uno dei 2 primi ancora a disposizione.
Bene, ora arriva la parte un po' più divertente... abbiamo tante belle condizioni per k, modulo 6 primi distinti, quindi per il TCR troviamo un k che va!
Puramente come curiosità, e c'è il 102% di probabilità che abbia sbagliato i conti, k=1930876 potrebbe anche funzionare
Ciao!
)Voglio dimostrarlo facendo i casi dei residui di n modulo 24.
Scopro che $ 2^{24}-1=3^2 \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 241 $.
Se prendo $ k \equiv 1 \pmod 3 $, allora $ k 2^{dispari} + 1 \equiv 2^{dispari} + 1 \equiv 2+1 \equiv 0 \pmod 3 $. E ciò ci leva tutti gli n dispari.
Prendo poi $ k \equiv 1 \pmod 5 $. Allora se $ n \equiv 2 \pmod 4 $ per lo stesso motivo di prima $ 5|2^n+1 $.
Ciò copre i residui dispari + 2,6,10,14,18,22
E avanti così a coprire residui! Via con $ k \equiv -1 \pmod {13} $, che copre 0 e 12 (perchè $ 2^{12k} \equiv 1 \pmod {13} $)
Con $ k \equiv 3 \pmod 7 $ copro $ n \equiv 4 \pmod 6 $
Avanzano solo 8 e 20 come residui, e 2 primi (17, 241). Dato che, modulo questi primi, 2 ha ordine che divide 24, posso aggiustarmi k in modo che se n è congruo a uno dei 2 residui mancanti modulo 24, allora il tutto è congruo a 0 modulo uno dei 2 primi ancora a disposizione.
Bene, ora arriva la parte un po' più divertente... abbiamo tante belle condizioni per k, modulo 6 primi distinti, quindi per il TCR troviamo un k che va!
Puramente come curiosità, e c'è il 102% di probabilità che abbia sbagliato i conti, k=1930876 potrebbe anche funzionare
Ciao!
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
Soluzione senza conti: (però trovata in ben più di 10 minuti...)
uso il fatto abbastanza noto che esiste un a tale che:
$ \displaystyle 2^{2^a} + 1 $ non è primo.
Prendo il più piccolo tale a.
Sia:
$ ~ p_1 = 2^{2^0} + 1 $
$ ~ p_2 = 2^{2^1} + 1 $
...
$ ~ p_{a} = 2^{2^{a-1}} + 1 $
Siano infine $ ~ p_{a+1}, p'_{a+1} $ due primi distinti che dividono $ \displaystyle 2^{2^a} + 1 $.
È noto che i $ ~ p_i $ saranno distinti, inoltre, l'ordine moltiplicativo di 2 modulo $ ~ p_i $ è proprio $ ~ 2^i $.
Quindi per ogni i posso trovare un $ ~ k_i $ tale che:
$ ~ p_i \mid k_i2^n + 1 \Leftrightarrow n \equiv 2^{i-1} \pmod {2^i} $.
Inoltre troviamo un $ ~ k'_{a+1} $ tale che:
$ ~ p'_{a+1} \mid k'_{a+1} 2^n + 1 \Leftrightarrow n \equiv 0 \pmod {2^i} $.
Sia k una soluzione positiva e grande al sistema di congruenze:
$ ~ k \equiv k_i \pmod {p_i} $ (i da 1 ad a+1)
$ ~ k \equiv k'_{a+1} \pmod {p'_{a+1}} $
Allora, per ogni n, a seconda della massima potenza di 2 che divide n, esisterà un unico dei primi da noi considerati che divide:
$ ~ k2^n + 1 $.
Siccome k è grande, allora $ ~ k2^n + 1 $ è grande, mentre i primi da noi considerati, essendo finiti, sono piccoli. Segue che $ ~ k2^n + 1 $ non è primo.
uso il fatto abbastanza noto che esiste un a tale che:
$ \displaystyle 2^{2^a} + 1 $ non è primo.
Prendo il più piccolo tale a.
Sia:
$ ~ p_1 = 2^{2^0} + 1 $
$ ~ p_2 = 2^{2^1} + 1 $
...
$ ~ p_{a} = 2^{2^{a-1}} + 1 $
Siano infine $ ~ p_{a+1}, p'_{a+1} $ due primi distinti che dividono $ \displaystyle 2^{2^a} + 1 $.
È noto che i $ ~ p_i $ saranno distinti, inoltre, l'ordine moltiplicativo di 2 modulo $ ~ p_i $ è proprio $ ~ 2^i $.
Quindi per ogni i posso trovare un $ ~ k_i $ tale che:
$ ~ p_i \mid k_i2^n + 1 \Leftrightarrow n \equiv 2^{i-1} \pmod {2^i} $.
Inoltre troviamo un $ ~ k'_{a+1} $ tale che:
$ ~ p'_{a+1} \mid k'_{a+1} 2^n + 1 \Leftrightarrow n \equiv 0 \pmod {2^i} $.
Sia k una soluzione positiva e grande al sistema di congruenze:
$ ~ k \equiv k_i \pmod {p_i} $ (i da 1 ad a+1)
$ ~ k \equiv k'_{a+1} \pmod {p'_{a+1}} $
Allora, per ogni n, a seconda della massima potenza di 2 che divide n, esisterà un unico dei primi da noi considerati che divide:
$ ~ k2^n + 1 $.
Siccome k è grande, allora $ ~ k2^n + 1 $ è grande, mentre i primi da noi considerati, essendo finiti, sono piccoli. Segue che $ ~ k2^n + 1 $ non è primo.