$p|2^q-1 \rightarrow p>q$

[Troleito br00tal]

Siano $p;q$ primi tali che $p|2^q-1$. Mostrare che $p>q$.

[Lasker]

Prima di tutto, visto che $2^q-1$ è dispari per ogni $q$, $p$ è sicuramente diverso da $2$.
Sappiamo inoltre che vale:
$$2^q\equiv 1 \pmod p$$
Dunque $ord_p(2)\mid q$ per definizione di ordine moltiplicativo.
Visto che $q$ è primo, l'ordine può valere solo $1\lor q$, ma il valore $1$ è assurdo, dunque $ord_p(2)=q$.
Ma dal piccolo teorema di Fermat sappiamo che $ord_p(2)\mid p-1$, dunque $q\mid p-1$ e quindi in particolare, visto che $p-1$ non è mai primo (se $p\ne 2$ come nelle ipotesi del problema) perché è divisibile per $2$, non c'è mai l'uguaglianza e vale:
$$p\mid 2^q-1\Rightarrow q\mid p-1 \Rightarrow p>q$$
Che è la tesi.

[jordan]

$p$ è chiaramente dispari, e in piu' $\alpha_n:=2^n-1$ è una sequenza di Mersenne (si chiama Lemma di Knuth se sbaglio), e per il teorema di Fermat $p$ divide $\alpha_{p-1}$. E' sufficiente a concludere che $p\mid \text{gcd}(\alpha_q,\alpha_{p-1})=\alpha_{\text{gcd}(p-1,q)}$, che implica $q \mid p-1$ visto che $\text{gcd}(p-1,q)$ non puo' essere $1$, e in particolare la tesi.

[Drago96]

$\alpha_n:=2^n-1$ è una sequenza di Mersenne (si chiama Lemma di Knuth se sbaglio)

Sì, esatto; in generale il cosiddetto Lemma di Knuth dice che $\gcd(x^n-1,x^m-1)=x^{\gcd(n,m)}-1$ (tra l'altro vale anche come identità di polinomi) e non è difficile dimostrarlo: dovrebbe bastare un'induzione.

Generalizzando mi pare si possa dire che ogni sequenza di Lucas sia anche una sequenza di Mersenne (apparve sul forum molto tempo fa, non so come dimostrarlo e non so nemmeno se ha un nome).
N.B: una sequenza di Lucas è una cosa del tipo $\displaystyle x_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}$ con $\alpha,\beta\in\mathbb C$; $\alpha\beta,\alpha+\beta\in\mathbb Z$ (e probabilmente per la validità del lemma serve anche $\gcd(\alpha\beta,\alpha+\beta)=1$ )
Osservazione: se $\alpha,\beta\in\mathbb R$ allora vale anche il teorema di Carmichael (su wikipedia c'è anche un link ad una dimostrazione che mi pare piuttosto elementare)

[Drago96]

Leggermente diverso:
Dobbiamo avere $\text{ord}_p(2)\mid\gcd(q,p-1)$. Se per assurdo $q\ge p$ allora $\gcd(q,p-1)=1$ e quindi $2^1\equiv1\pmod p$, che è assurdo.