Il povero 41
Uno dei problemi di ammissione alla Normale (1994) recita
"Mostrare che 41 non può essere espresso come differenza di una potenza di 2 e una di 3, cioè che non sussiste nessuna delle due uguaglianze
$41=2^n-3^m$ $41=3^n-2^m$
per $m$ e $n$ interi positivi"
Ho provato l'asserto per induzione nel caso $m=n$ ma non saprei continuare nel caso $n>m$ o $n
Grazie a chi risponderà e buon divertimento
"Mostrare che 41 non può essere espresso come differenza di una potenza di 2 e una di 3, cioè che non sussiste nessuna delle due uguaglianze
$41=2^n-3^m$ $41=3^n-2^m$
per $m$ e $n$ interi positivi"
Ho provato l'asserto per induzione nel caso $m=n$ ma non saprei continuare nel caso $n>m$ o $n
Grazie a chi risponderà e buon divertimento
Risposte
Fissi uno e procedi con induzione sull'altro ...
@axpgn
Seguendo il tuo consiglio mi sono bloccato.
Fissiamo $m$ e mostriamo che $2^n-3^m$ non è divisibile per 41. Infatti per $n=1$ si ha $39=3^m$ che non ha soluzioni intere per $m$. Supponiamo che sia vera per $n$ e dimostriamo l'asserto per $n+1$.
$2^(n+1)-3^m=2*2^n-3^m=(41-39)*2^n-3^m=41*2^n-39*2^n-3^m= 41*2^n+(2^n-3^m)-40*2^n$
Qui però mi blocco: come faccio a sfruttare il fatto che $2^n-3^m$ non divide 41?
Mi puoi aiutare?
Seguendo il tuo consiglio mi sono bloccato.
Fissiamo $m$ e mostriamo che $2^n-3^m$ non è divisibile per 41. Infatti per $n=1$ si ha $39=3^m$ che non ha soluzioni intere per $m$. Supponiamo che sia vera per $n$ e dimostriamo l'asserto per $n+1$.
$2^(n+1)-3^m=2*2^n-3^m=(41-39)*2^n-3^m=41*2^n-39*2^n-3^m= 41*2^n+(2^n-3^m)-40*2^n$
Qui però mi blocco: come faccio a sfruttare il fatto che $2^n-3^m$ non divide 41?
Mi puoi aiutare?
"Cantor99":
@axpgn
Seguendo il tuo consiglio mi sono bloccato.
"Cantor99":
Mi puoi aiutare?
Non saprei ... dovrei pensarci ma non garantisco niente ...
... comunque secondo me il passo base deve essere $n=m$ (e salire con $n$) che hai detto di aver già dimostrato ...Cordialmente, Alex
Avevo provato che $2^n-3^n$ è sempre divisibile per 5 (per induzione) e quindi non può essere divisibile per 41 essendo impossibile $5k=41$
...
Comunque mi sa che ho sbagliato sezione...come faccio a cambiare?
...
Comunque mi sa che ho sbagliato sezione...come faccio a cambiare?
Chiedi a un moderatore di spostarlo ...
va bene algebra, teoria deinumeri e matematica discreta?
Per me dovrebbe andare in "Scervelliamoci un po'", sono lì i problemi di questo tipo ...
[xdom="Raptorista"]Sposto da Analisi si base.[/xdom]
Caso $41=3^m-2^n$
In tal caso $m$ e $n$ devono essere necessariamente pari, infatti
\begin{equation}
41 \equiv 2 \equiv -2^n \equiv -1 \mod 3
\end{equation}
da cui $n$ pari (piccolo teorema di Fermat) analogamente riducendo modulo 4 si ha $m$ pari. Dunque possiamo scrivere $m=2k$ e $n=2h$,con $h,k \in \mathbb{N}$, dunque con qualche passaggio (slavo conti errati) si ha
\begin{equation}
41=(3^k-2^h+2^{h+1})(3^k-2^h)
\end{equation}
da cui essendo 41 primo si ha necessariamente che $3^k-2^h+2^{h+1}=41$ e $3^k-2^h=1$ ma $(3^k-2^h)^2=41-2^{h+1}3^k=1$, assurdo.
Per l'altro caso basta ridurre modulo 3 e 2 mostrando che $m$ e $n$ sono necessariamente dispari, quindi scrivere $m=2k+1$ e $n=2h+1$ e ridurre modulo 8
In tal caso $m$ e $n$ devono essere necessariamente pari, infatti
\begin{equation}
41 \equiv 2 \equiv -2^n \equiv -1 \mod 3
\end{equation}
da cui $n$ pari (piccolo teorema di Fermat) analogamente riducendo modulo 4 si ha $m$ pari. Dunque possiamo scrivere $m=2k$ e $n=2h$,con $h,k \in \mathbb{N}$, dunque con qualche passaggio (slavo conti errati) si ha
\begin{equation}
41=(3^k-2^h+2^{h+1})(3^k-2^h)
\end{equation}
da cui essendo 41 primo si ha necessariamente che $3^k-2^h+2^{h+1}=41$ e $3^k-2^h=1$ ma $(3^k-2^h)^2=41-2^{h+1}3^k=1$, assurdo.
Per l'altro caso basta ridurre modulo 3 e 2 mostrando che $m$ e $n$ sono necessariamente dispari, quindi scrivere $m=2k+1$ e $n=2h+1$ e ridurre modulo 8
@dan95 come sempre mi sei di grande aiuto e non finirò mai di ringraziarti...
Passando alla tua dimostrazione ho dei dubbi sulla (1):
a) Allora è vero che $41-=2 mod 3$ così come $41-= -1 mod 3$ e $41-= -2^m mod 3$. Per scrivere la (1) hai applicato la proprietà transitiva? (scusa la domanda banale ma è da poco che mastico l'aritmetica modulare)
b) so che il piccolo teorema di Fermat afferma che per ogni $a$ intero e $p$ primo si ha $a^p-= a mod p$. Come puoi aver dedotto dalla (1) e dal succitato teorema che $m$ è pari?
Passando alla tua dimostrazione ho dei dubbi sulla (1):
a) Allora è vero che $41-=2 mod 3$ così come $41-= -1 mod 3$ e $41-= -2^m mod 3$. Per scrivere la (1) hai applicato la proprietà transitiva? (scusa la domanda banale ma è da poco che mastico l'aritmetica modulare)
b) so che il piccolo teorema di Fermat afferma che per ogni $a$ intero e $p$ primo si ha $a^p-= a mod p$. Come puoi aver dedotto dalla (1) e dal succitato teorema che $m$ è pari?
a) Sì
b) Se $a$ è coprimo con 3 allora per Fermat abbiamo che $a^2 \equiv 1 \mod 3$ in generale ogni potenza di $a$ è coprima con 3, dunque $a^{2k} \equiv 1 \mod 3$. Se prendiamo $a=2$ abbiamo che $2^{2k} \equiv 1 \mod 3$, ma la (1) dice proprio questo e quindi $n$ è necessariamente pari. Per mostrare che $m$ è anche pari segui lo stesso ragionamento applicando il teorema più generale di Eulero (vedi Wikipedia)
b) Se $a$ è coprimo con 3 allora per Fermat abbiamo che $a^2 \equiv 1 \mod 3$ in generale ogni potenza di $a$ è coprima con 3, dunque $a^{2k} \equiv 1 \mod 3$. Se prendiamo $a=2$ abbiamo che $2^{2k} \equiv 1 \mod 3$, ma la (1) dice proprio questo e quindi $n$ è necessariamente pari. Per mostrare che $m$ è anche pari segui lo stesso ragionamento applicando il teorema più generale di Eulero (vedi Wikipedia)
@ Cantor99
_______
??_______
@Erasmus_first
Sì adesso che me lo fai notare ho fatto un'errore abbastanza grossolano (oltre il non aver controllato per altri $n$...)
avevo posto $n=2$ ottenendo una verità. Poi l'ho supposto vero per $n$ e volevo dimostrare che
$3*3^n-2*2^n= (5-2)*3^n-2^n= 5*3^n-2*(3^n+2^n)$
Ora nella parentesi avevo scritto $3^n-2^n$, ecco l'errore...
Grazie per avermelo fatto notare
@dan chiarissimo, in pratica hai usato la forma $a^(p-1)-=1 mod p$ che è applicabile nel nostro caso.
Mentre per dimostrare che $m$ (seguendo il tuo consiglio) partirei dall'uguaglianza
$41-= 3^m -= 1 mod 2$ $(3)$
Da cui abbiamo $3^m -= 1 mod 2$. Come dovrei applicare la generalizzazione del piccolo teorema di Fermat (se la strada che ho iniziato è questa)?
Sì adesso che me lo fai notare ho fatto un'errore abbastanza grossolano (oltre il non aver controllato per altri $n$...)
avevo posto $n=2$ ottenendo una verità. Poi l'ho supposto vero per $n$ e volevo dimostrare che
$3*3^n-2*2^n= (5-2)*3^n-2^n= 5*3^n-2*(3^n+2^n)$
Ora nella parentesi avevo scritto $3^n-2^n$, ecco l'errore...
Grazie per avermelo fatto notare
@dan chiarissimo, in pratica hai usato la forma $a^(p-1)-=1 mod p$ che è applicabile nel nostro caso.
Mentre per dimostrare che $m$ (seguendo il tuo consiglio) partirei dall'uguaglianza
$41-= 3^m -= 1 mod 2$ $(3)$
Da cui abbiamo $3^m -= 1 mod 2$. Come dovrei applicare la generalizzazione del piccolo teorema di Fermat (se la strada che ho iniziato è questa)?
@Cantor
Se vuoi entrare alla SNS alcune domande non dovresti nemmeno farle.
Detto questo, la riduzione è modulo 4 e non 2.
Se vuoi entrare alla SNS alcune domande non dovresti nemmeno farle.
Detto questo, la riduzione è modulo 4 e non 2.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo