[Ammissione WC16] TdN 2: $n$ non primo divide $3^{n-1}-2^{n-1}$

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

[Ammissione WC16] TdN 2: $n$ non primo divide $3^{n-1}-2^{n-1}$

Messaggio da Talete » 30 dic 2015, 22:49

NON pubblicate la soluzione prima delle 23:59 di oggi!

Dimostrare che esistono infiniti interi positivi composti $n$ tali che $n$ divida $3^{n-1}-2^{n-1}$.
"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

Giovanni_98
Messaggi: 69
Iscritto il: 10 apr 2015, 18:19

Re: [Ammissione WC16] TdN 2: $n$ non primo divide $3^{n-1}-2^{n-1}$

Messaggio da Giovanni_98 » 31 dic 2015, 13:55

Testo nascosto:
Prendiamo $n=3^{2^k}-2^{2^k}$ con $k$ intero $\ge 2$. Notiamo che $$n=\prod_{i=0}^{k-1}( 3^{2^i} + 2^{2^i} )$$poichè $k \ge 2$ i termini della produttoria maggiori di $1$ sono almeno $2$ e quindi $n$ è composto.

Lemma : $v_2(3^{3^{2^k}-2^{2^k}-1}-2^{3^{2^k}-2^{2^k}-1}-1)=k+2$ per qualsiasi $k \ge 2 $ intero.
Dimostrazione : Dal momento che $2^{k+2} \leq 2^{2^k}$ (si dimostra banalmente per induzione) è sufficiente dimostrare che $2^{k+2} \mid \mid 3^{2^k}-1$. Riscrivo come $2^{k+2} \mid\mid 9^{2^{k-1}}-1$. Dal momento che $4 \mid 9-1$ posso applicare LTE e quindi $v_2(9^{2^{k-1}}-1) = v_2(8) + v_2(2^{k-1}) = k+2$.

Scriviamo $n=2^{k+2} \cdot q$ con $(q,2)=1$ per il lemma precedente. Allora deve valere $$3^{2^k}-2^{2^k} \mid 3^{2^{k+2}\cdot q} - 2^{2^{k+2}\cdot q}$$Dal momento che $q$ è dispari si ha che $3^{2^{k+2}}-2^{2^{k+2}} \mid 3^{2^{k+2}\cdot q} - 2^{2^{k+2}\cdot q}$ ma $$3^{2^{k+2}}-2^{2^{k+2}}=(3^{2^{k+1}}-2^{2^{k+1}})(3^{2^{k+1}}+2^{2^{k+1}})=(3^{2^{k}}-2^{2^{k}})(3^{2^{k}}+2^{2^{k}})(3^{2^{k+1}}+2^{2^{k+1}})$$e quindi la tesi è dimostrata.

Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Re: [Ammissione WC16] TdN 2: $n$ non primo divide $3^{n-1}-2^{n-1}$

Messaggio da Troleito br00tal » 31 dic 2015, 14:05

Per i più coraggiosi: provate a risolverlo con le proprietà dei polinomi ciclotomici!

Hanno anche aperto apposta un bel thread

viewtopic.php?f=26&t=19719

Saro00
Messaggi: 114
Iscritto il: 27 mag 2015, 10:52
Località: Provincia di Milano

Re: [Ammissione WC16] TdN 2: $n$ non primo divide $3^{n-1}-2^{n-1}$

Messaggio da Saro00 » 31 dic 2015, 14:16

Sapevo che poteva venire con quei famigerati polinomi, ora che l'hai detto proveró.
Metto in spoiler 3 idee per risolverlo
Testo nascosto:
$ n=3^{2^n}-2^{2^n} \forall n \in \mathbb{N} n\ge 2 $
Testo nascosto:
$ n=3^{3^n}-2^{3^n} \forall n \in \mathbb{N} n\ge 2 $
Testo nascosto:
$ n=3^{p}-2^{p} \forall n \in \mathbb{P} $ e per garantire la primalitá di $ n $ lo mettiamo congruo a 2 o 4 modulo 5 (serve peró Dirichlet)
Un giorno di questi mi metteranno in prigione per aver stuprato troppi problemi. 8)

Rispondi