BST 2009/2 (ITA)

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

BST 2009/2 (ITA)

Messaggio da Karl Zsigmondy » 07 ott 2011, 17:05

Trovare tutti gli n interi positivi per cui esiste m intero positivo tali che:
$ \displaystyle\frac{4^n-1}{3} \mid (49m^2 + 1). $

L'ho postato perché si sfrutta un'idea (o tecnica, come la si vuole chiamare) abbastanza interessante. O almeno nella mia dimostrazione. Si accettano anche spunti.

EDIT: piccola modifica di leggibilità. ma_go
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"

Avatar utente
Tess
Messaggi: 247
Iscritto il: 15 set 2009, 14:20
Località: Maserada s. P.

Re: BST 2009/2 (ITA)

Messaggio da Tess » 07 ott 2011, 17:42

Il 49 è messo lì per bellezza?

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: BST 2009/2 (ITA)

Messaggio da xXStephXx » 07 ott 2011, 17:49

Per ora so solo che la parte che sta a sinistra corrisponde alla somma delle potenze di 4 con esponente che va da 0 a n-1.

Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

Re: BST 2009/2 (ITA)

Messaggio da Karl Zsigmondy » 08 ott 2011, 14:04

Tess ha scritto:Il 49 è messo lì per bellezza?
Poteva esserci anche 121.
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"

stergiosss
Messaggi: 48
Iscritto il: 07 set 2011, 20:26

Re: BST 2009/2 (ITA)

Messaggio da stergiosss » 08 ott 2011, 15:21

Ecco, qui si che un hint mi farebbe comodo :P

paga92aren
Messaggi: 358
Iscritto il: 31 lug 2010, 10:35

Re: BST 2009/2 (ITA)

Messaggio da paga92aren » 08 ott 2011, 19:25

Riscrivo il testo come $4^n-1|3((7m)^2+1)$ quindi $9\nmid 4^n-1$ da cui $3\nmid n$.
Prendo un primo $p\not=3$ tale che $p|4^n-1$ allora $(7m)^2\equiv -1\mod p$ quindi ord$_p(7m)=4|p-1$ da cui $p\equiv 1 \mod 4$.
Inoltre $2^{2n}-1=(2^n+1)(2^n-1)$ se $n$ dispari $3|2^n+1$ quindi $2^n-1$ ha fattori primi solo congrui a 1 modulo 4 quindi $2^n-1\equiv 1\mod 4$ quindi $n=1$.
Altrimenti $n=2n'$ e $2^{4n'}-1=(2^{2n'}+1)(2^{2n'}-1)$ e ripeto il ragionamento sul secondo fattore. Conclusione $n=2^k$.
Infine verifico che esiste $m$ per ogni $k$: per ogni $p|\frac{2^{2^k}-1}{3}$ vale che $p\equiv 1 (4)$ e basta verificare che -1 è un residuo modulo $p$ che è vero per la reciprocità quadratica (esiste l'inverso modulo $p$ per aggiustare il 7 e si conclude col teorema cinese del resto), quindi esiste $m$ opportuno.

Avatar utente
Karl Zsigmondy
Messaggi: 138
Iscritto il: 09 lug 2011, 14:32
Località: Città di Altrove, Kansas

Re: BST 2009/2 (ITA)

Messaggio da Karl Zsigmondy » 09 ott 2011, 09:25

Perfetto! Un modo leggermente più veloce per escludere le non potenze di 2 era sfruttare il fatto che se d dispari divide n allora $ (4^d - 1) \mid (4^n-1) $, e da lì trattare WLOG il caso dispari come hai fatto tu. Anche se hai fatto a livello di idea la stessa cosa.
"Un matematico è una macchina che converte caffè in teoremi."
"Life is very short and there's no time for fussing and fighting, my friend!"

Rispondi