Problema #1: mostrare che, per un qualche $ v \in\mathbb{N}_0 $ e per ogni intero $ n > v $, esiste $ p\in\mathfrak{P} $ tale che $ p \mid (2^{\varphi(n)} - 1) $ e $ p\nmid n $.
Nota: prima che lo si domandi, $ \mathfrak{P} $ denota qui l'insieme di tutti e soli i numeri primi di $ \mathbb{N} $.
Sui divisori primi di n e di 2^phi(n) - 1.
-
Gottinger95
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: Sui divisori primi di n e di 2^phi(n) - 1.
Poniamo \(n= \prod_{i=1}^k p_k^{\alpha_k} \). Per ogni \(p_i \neq 2 \), definiamo \(r_i = \sum_{j \neq i} V_{p_i} ( p_j-1) \).
1.Notiamo che
\[ \prod_{i=1}^k p_i^{r_i} < \prod_{i=1}^k (p_i-1) \]
da cui
\[ \prod_{i=1}^k p_i^{\alpha_i + r_i} < \varphi(n) P(n) < \varphi(n)^3\]
dove \(P(n) = \prod_{p \mid n} p \).
2. Anzitutto notiamo (banalmente, però tocca dirlo) che \(V_2(2^{\varphi(n)}-1) = 0 \).
Vogliamo dimostrare adesso che per \(p_i \neq 2\) vale \( V_{p_i} ( 2^{\varphi(n)}-1) \le \alpha_i + r_i \). Supponiamo per assurdo che
\[ 2^{\varphi(n)} \equiv 1 \pmod{ p_i^{\alpha_i+r_i+1} } \]
da cui
\[ \varphi(n) = p_i^{\alpha_i-1}(p-1) \prod_{j \neq i} p_j^{\alpha_j} (p_j-1) \equiv 0 \pmod{ p_i^{\alpha_i+r_i}(p_i-1) } \]
Affinchè questo accada, si deve avere \( p_i^{r_i+1} \mid \prod_{j \neq i} p_j^{\alpha_j} (p_j-1) \); d'altronde \(p_i \nmid p_j^{\alpha_j}\), e per definizione \(V_{p_i}( \prod_{j \neq i} (p_j-1)) = r_i < r_i +1\), assurdo.
3. Esiste un intero \(v\) tale che per ogni \(n \ge v\) si ha \(2^{\varphi(n)}-1 > \varphi(v)^3\); questo perchè LHS è esponenziale e RHS è polinomiale, in \(\varphi(n)\).
Conclusione.
Scriviamo
\[ 2^{\varphi(n)}-1 = \left ( \prod_{p_i \mid n} p_i^{\beta_i} \right) \cdot \left ( \prod_{q_j \in S} q_j^{\gamma_j} \right ) \]
dove \(S\) è l'insieme dei primi che dividono \(2^{\varphi(n)}-1\) ma non \(n\). La tesi è che \(S\) sia non-vuoto. Per il punto \(2\), abbiamo \(\beta_i \le \alpha_i+r_i\), da cui, per il punto (1):
\[ 2^{\varphi(n)}-1 = \left ( \prod_{p_i \mid n} p_i^{\beta_i} \right) \cdot \left ( \prod_{q_j \in S} q_j^{\gamma_j} \right ) \le \varphi(n)^3 \cdot \left ( \prod_{q_j \in S} q_j^{\gamma_j} \right ) \]
Per il punto 3, per ogni \(n \ge v\) vale dunque :
\[ \left ( \prod_{q_j \in S} q_j^{\gamma_j} \right ) \ge \frac{ 2^{\varphi(n)}-1}{\varphi(n)^3} > 1\]
ossia \(S\) è non-vuoto, Q.E.D.
EDIT: Niente, ho stratoppato; ho assunto che 2 fosse generatore mod \(p^{\alpha_i+r_i+1}\), cosa che mi sono assolutamente inventato
1.Notiamo che
\[ \prod_{i=1}^k p_i^{r_i} < \prod_{i=1}^k (p_i-1) \]
da cui
\[ \prod_{i=1}^k p_i^{\alpha_i + r_i} < \varphi(n) P(n) < \varphi(n)^3\]
dove \(P(n) = \prod_{p \mid n} p \).
2. Anzitutto notiamo (banalmente, però tocca dirlo) che \(V_2(2^{\varphi(n)}-1) = 0 \).
Vogliamo dimostrare adesso che per \(p_i \neq 2\) vale \( V_{p_i} ( 2^{\varphi(n)}-1) \le \alpha_i + r_i \). Supponiamo per assurdo che
\[ 2^{\varphi(n)} \equiv 1 \pmod{ p_i^{\alpha_i+r_i+1} } \]
da cui
\[ \varphi(n) = p_i^{\alpha_i-1}(p-1) \prod_{j \neq i} p_j^{\alpha_j} (p_j-1) \equiv 0 \pmod{ p_i^{\alpha_i+r_i}(p_i-1) } \]
Affinchè questo accada, si deve avere \( p_i^{r_i+1} \mid \prod_{j \neq i} p_j^{\alpha_j} (p_j-1) \); d'altronde \(p_i \nmid p_j^{\alpha_j}\), e per definizione \(V_{p_i}( \prod_{j \neq i} (p_j-1)) = r_i < r_i +1\), assurdo.
3. Esiste un intero \(v\) tale che per ogni \(n \ge v\) si ha \(2^{\varphi(n)}-1 > \varphi(v)^3\); questo perchè LHS è esponenziale e RHS è polinomiale, in \(\varphi(n)\).
Conclusione.
Scriviamo
\[ 2^{\varphi(n)}-1 = \left ( \prod_{p_i \mid n} p_i^{\beta_i} \right) \cdot \left ( \prod_{q_j \in S} q_j^{\gamma_j} \right ) \]
dove \(S\) è l'insieme dei primi che dividono \(2^{\varphi(n)}-1\) ma non \(n\). La tesi è che \(S\) sia non-vuoto. Per il punto \(2\), abbiamo \(\beta_i \le \alpha_i+r_i\), da cui, per il punto (1):
\[ 2^{\varphi(n)}-1 = \left ( \prod_{p_i \mid n} p_i^{\beta_i} \right) \cdot \left ( \prod_{q_j \in S} q_j^{\gamma_j} \right ) \le \varphi(n)^3 \cdot \left ( \prod_{q_j \in S} q_j^{\gamma_j} \right ) \]
Per il punto 3, per ogni \(n \ge v\) vale dunque :
\[ \left ( \prod_{q_j \in S} q_j^{\gamma_j} \right ) \ge \frac{ 2^{\varphi(n)}-1}{\varphi(n)^3} > 1\]
ossia \(S\) è non-vuoto, Q.E.D.
EDIT: Niente, ho stratoppato; ho assunto che 2 fosse generatore mod \(p^{\alpha_i+r_i+1}\), cosa che mi sono assolutamente inventato
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe