Stage Senior 2006, TDN 1 - Es. 7

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Pigkappa
Messaggi: 1208
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Stage Senior 2006, TDN 1 - Es. 7

Messaggio da Pigkappa » 18 set 2006, 17:19

Per ogni intero positivo, sia $ d_n=(n^2+100, (n+1)^2 +100) $. Determinare il massimo valore possibile per $ d_n $







[No, non sono sadico a riproporre lo stesso esercizio dopo pochi giorni che è stato fatto... Solo che volevo vedere una soluzione perchè il risultato sarebbe 401, mentre io arrivo a trovare 200,5, che tra l'altro non ha neanche molto senso]

sqrt2
Messaggi: 142
Iscritto il: 19 gen 2006, 14:43
Località: Genova

Messaggio da sqrt2 » 18 set 2006, 19:12

Algoritmo euclideo: $ d_n = (n^2 + 100, 2n + 1) $.
Ora siccome $ 2n + 1 $ è sempre dispari si ha
$ d_n = (2n^2 + 200,2n + 1) = (2n + 1, -n + 200) = 401 $

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager » 18 set 2006, 21:10

in realta' adesso dovresti dimostrare che il massimo che hai trovato e' ottenibile...

Avatar utente
Ponnamperuma
Messaggi: 411
Iscritto il: 10 lug 2006, 11:47
Località: Torino

Messaggio da Ponnamperuma » 18 set 2006, 22:32

$ (200^2+100,201^2+100)=401 $... vedi dispense di D.Santos... capitolo 4! :)
Quello che mi sfugge è come si può dire che il massimo sia proprio 401... voglio dire, non avrei potuto ottenere qualche altro numero con opportune manipolazioni tra le parentesi dei gcd? O l'esigenza di eliminare le n conduce univocamente a questo risultato :?: Scusate l'ignoranza, ma... :roll:

EvaristeG
Site Admin
Messaggi: 4750
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 18 set 2006, 22:51

Penso che su questo il povero marco si sia profuso in spiegazioni : tutti questi passaggi dimostrano che l'mcd divide 401 ... a questo punto bisogna esibire la coppia che lo realizza.

Avatar utente
Ponnamperuma
Messaggi: 411
Iscritto il: 10 lug 2006, 11:47
Località: Torino

Messaggio da Ponnamperuma » 18 set 2006, 22:53

scusa, sono un pirla... me ne sono or ora reso conto! :lol:
Ciao!

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager » 19 set 2006, 12:30

posto anche la mia soluzione che e' un po' diversa e permette di trovare anche la n giusta....
abbiamo
$ n^2+100\equiv (n+1)^2+100\equiv 0 $ $ mod(d_n) $
$ 0\equiv 2n+1 $
$ n\equiv -1/2 $ ($ d_n $ e' dispari)
sostituendo per n abbiamo
$ 1/4+100\equiv 0 $ $ mod(d_n) $
$ 100\equiv -1/4 $ quindi $ 401\equiv0 $
dunque $ d_n|401 $ e per ottenere 401 e' sufficiente sostituire $ n=(401-1)/2=200 $

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 19 set 2006, 15:30

Ponnamperuma ha scritto:Quello che mi sfugge è come si può dire che il massimo sia proprio 401... voglio dire, non avrei potuto ottenere qualche altro numero con opportune manipolazioni tra le parentesi dei gcd?
Il modo più semplice è sfruttare l'identità di Bézout: Se chiami a e b i due numeri incriminati, scopri (ad es. facendo girare l'algoritmo di Euclide esteso), che

401 = (2n+3)a + (1-2n)b.

Durante la lezione si è detto che l'MCD è il minimo positivo di tutte le combinazioni "alla Bézout", e ogni altro valore è multiplo dell'MCD. Ne segue che necessariamente 401 è multiplo dell'MCD.

A questo punto devi esibire un esempio. Come lo trovi?

Beh, se hai seguito bene tutto il giro del fumo, sai che

(a,b) = (a [oppure b], 2n + 1)

Necessariamente devi avere che 2n+1 sia quanto meno multiplo di 401 e la scelta più ovvia è provare con n=200.

A questo punto rilancio l'esercizio:

Bonus question: Calcolare i valori di n per cui risulta MCD = 401.

HINT:
In realtà il problema è già stato risolto in questo stesso thread...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 19 set 2006, 15:35

sqrt2 ha scritto:$ (2n + 1, -n + 200) = 401 $
mmm.... Quest'ultima uguaglianza non è vera sempre (altrimenti proveresti che l'MCD fa 401 sempre).

La cosa che si può affermare è
$ (2n + 1, -n + 200) = (401, 2n+1) = (401, -n+200) $
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

sqrt2
Messaggi: 142
Iscritto il: 19 gen 2006, 14:43
Località: Genova

Messaggio da sqrt2 » 19 set 2006, 15:50

Marco ha scritto:mmm.... Quest'ultima uguaglianza non è vera sempre (altrimenti proveresti che l'MCD fa 401 sempre).
Sì hai ragione; io intendevo il $ d_n $ massimo.

Rispondi