Stage Senior 2006, TDN 1 - Es. 7

[Pigkappa]

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]

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]

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

[Ponnamperuma]

$ (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...

[EvaristeG]

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.

[Ponnamperuma]

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

[matthewtrager]

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 $

[Marco]

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...

[Marco]

$ (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) $

[sqrt2]

mmm.... Quest'ultima uguaglianza non è vera sempre (altrimenti proveresti che l'MCD fa 401 sempre).

Sì hai ragione; io intendevo il $ d_n $ massimo.