$2^k-m$ ha almeno $n$ divisori primi distinti

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

$2^k-m$ ha almeno $n$ divisori primi distinti

Messaggio da jordan » 11 ott 2015, 21:09

Non ricordo se è già passato da queste parti (forse è passata una volta una versione piu' generale, ma di quella sono abbastanza sicuro di non aver visto soluzioni..) In ogni caso, questa è presa dal TST cinese anno 2006:

Siano $m,n$ interi positivi fissati. Mostrare che esiste un intero positivo $k$ tale che $2^k-m$ ha almeno $n$ divisori primi distinti.
The only goal of science is the honor of the human spirit.

LucaMac
Messaggi: 174
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: $2^k-m$ ha almeno $n$ divisori primi distinti

Messaggio da LucaMac » 11 ott 2015, 22:04

Sperando di non dire cose errate, mi sembra fattibile per essere un TST cinese, è un 1?
Sia $ \omega(x) $ il numero di divisori primi distinti di $x$.
Il contrario della tesi è ovviamente $ \omega(2^k -m) $ limitato al variare di $k$. Supponiamo quindi per assurdo che sia limitato e di massimo $r$. WLOG $m$ dispari (altrimenti divido per $2^{v_2(m)} $ ).
Prendiamo ora $t$ tale che $\omega(2^t-m) = r $ ovvero $ 2^t-m= \prod_{i=1}^r p_i^{\alpha_i } $ con $p_i $ primi dispari e $2<p_1 < \ldots < p_r$ e $\alpha_i \geq 1$. Sia $s= \prod_{i=1}^r (p_i-1) $. Notiamo che $2^s \equiv 1 \pmod{p_i} $ $ \forall i$ da cui $ p_i \mid 2^{t+s} $ $ \forall i $ ($2^{t+s} \equiv 2^t \pmod{p_i} $ ). Allora, ripetendo il ragionamento, essendo $r$ il massimo ,si deve avere che questi sono gli unici fattori primi di $2^k -m$ per $k=t,t+s,t+2s \ldots $.
Prendiamo ora un qualsiasi $a$ ed un $y \geq p_r^{ra}$ , da cui $ A=2^{t+ys}-m \geq 2^{ys} \geq 2^y \geq p_r^{ra} $ . Allora, ricordando che i fattori primi di $A$ sono solo quelli, si ha che il massimo esponente tra loro è $ \geq a$. Considerando $y,y+1, \ldots , y+r$ questa cosa ovviamente continua a valere. In particolare ne esisteranno che hanno lo stesso primo che realizza il massimo, diciamo con indice $i$. Allora esistono $u>v$ con $u-v \leq rs$ tali che (visto che il massimo è $ \geq a $ ) $$p_i^a \mid 2^u-m$$ e $$p_i^a \mid 2^v - m$$ da cui $$p_i^a \mid 2^u-2^v $$ ovvero essendo $p_i$ dispari si ha $$p_i^a \mid 2^{u-v}-1$$ che implica (essendo $u>v$) $$p_i^a \leq 2^{u-v}-1 \leq 2^{rs}-1$$ , ma essendo $p_i \geq 3$ per $a$ sufficientemente grande si ha un assurdo.
Allora la tesi deve essere necessariamente vera :D
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $2^k-m$ ha almeno $n$ divisori primi distinti

Messaggio da jordan » 12 ott 2015, 01:25

Scritto quasi come flusso di coscienza, ma le idee ci sono tutte :wink:

Ps. Non direi, giorno 6 problema 2!
The only goal of science is the honor of the human spirit.

Rispondi