Provinciali 2005 n. 10

[domx]

Siano a, b interi positivi primi tra loro. Qual è il massimo valore che può assumere il massimo comun divisore fra (a+b)^4 e a-b?
(A) 3 (B) 4 (C) 16 (D) 32 (E) può essere grande a piacere
La risposta è la C.

Ragazzi, mi spieghereste questo esercizio? Dalle soluzioni non ci ho capito molto, ed in teoria dei numeri, avendola iniziato a studiare da poco, non sono molto ferrato...
ciao e grazie

[Veluca]

Andiamo bovinamente di conti
(qui sfrutto numerose volte il fatto che $(a,b)=(a+kb,b)$)
$((a+b)^4,a-b)=((a+b)^4-(a-b)^4,a-b)=([(a+b)^2+(a-b)^2][(a+b)+(a-b)][(a+b)-(a-b)],a-b)=(8ab(a^2+b^2),a-b)=(8ab(a^2+b^2)-8ab(a-b)^2,a-b)=(16ab,a-b)$
Ora se un primo p divide a, allora p non divide b (questo perchè $(a,b)=1$) .. di conseguenza p non divide a-b. Analogamente anche se p divide b, p non divide a-b.
Quindi $ab$ è coprimo con $a-b$, e quindi posso toglierlo: $(16ab,a-b)=(16,a-b)$. Ora questo mcd deve dividere 16, quindi è 1,2,4,8, o 16.

PS: nel caso non avessi mai visto questa notazione, con $(a,b)$ si indica l'mcd di a e b.

[LukasEta]

Io direi allora...
L''MCD cercato è il massimo numero che divide sia $ a-b $ sia $ (a+b)^4 $
Chiamo l'MCD ---> $ x $

Se $ x $ divide $ a-b $, posso scrivere che $ a-b \equiv 0 \mod x $ => $ a \equiv b \mod x $

Siccome x divide anche $ (a+b)^4 $, allora $ (a+b)^4 \equiv 0 \mod x $

Abbiam detto che $ a \equiv b \mod x $, per cui $ (b+b)^4 \equiv 0 \mod x $ => $ 16b^4 \equiv 0 \mod x $

Quest'ultima congruenza mi dice che per x=16, otterrò sempre resto 0, il che ci piace. Però anche $ b^4 $ , se fosse divisibile per x, renderebbe la congruenza sempre verificata => ecco che entra in gioco il fatto che il testo ci dice che i due numeri sono primi tra loro .
Infatti nel caso in cui fosse $ b \equiv 0 \mod x $ , tornando al numero $ a-b $ e sostituendo, otterrei $ a-0 \equiv 0 \mod x $, da cui $ a \equiv 0 \mod x $

Ma allora x sarebbe divisore sia di a che di b, il che significherebbe che i nostri a e b non sarebbero primi tra di loro. Allora per x=16 abbiamo il massimo valore per cui la nostra congruenza $ 16b^4 \equiv 0 \mod x $ è verificata. Tutto chiaro? Vedi quanto servono le congruenze? xD

PS: se avessi fatto qualche errore ci sta, vista l'ora :S In caso scusate xD

PPS: la soluzione ufficiale non l'ho capito nemmeno io

[Claudio.]

Nell'area download del sito manca l'anno 2005

[LukasEta]

Nell'area download del sito manca l'anno 2005

Fatto strano: se scarichi dal sito "Cesenatico 2005" ti arriva uno zip che contiene sia Cesenatico 2005 che Febbraio 2005. Provare per credere

[domx]

Ragazzi, grazie mille per le risposte. La risposta di veluca non sono riuscito a comprenderla, mentre quella di LukasEta l'ho capita, il punto è che credo difficilmente se mi troverò un problema simile giovedì riuscirò a risolverlo...
mi postereste qualche esercizio simile in modo che possa cimentarmi e magari, allenandomi, riuscire a fare davvero mio il concetto di congruenza?
Vi ringrazio in anticipo, meno male che c'è l'oliforum

edit: ah, comunque io la scheda di febbraio 2005 l'ho scaricata da qui...

[ma_go]

mi pare che usare le congruenze sia proprio sprecato. meglio usare fatterelli tipo quelli che ha usato Veluca, magari in modo più furbo

cose che uno dovrebbe sapere e/o vedere a occhio:
A. se $a$ e $b$ sono coprimi, allora $MCD(a+b,a-b)$ divide 2 (cioè è 1 o 2).
B. se $d=MCD(m,n)$, allora $MCD(m,n^k) = MCD(m,d^k)$, e quest'ultimo divide $d^k$.
mettendo insieme A e B, segue immediatamente che $MCD((a+b)^4,a-b)$ divide 16. poi bisogna trovare un esempio che effettivamente realizza 16, e questo richiede un minimo (davvero minimo!) di intuizione, o di ragionamento su quando i "divide" in A e B possono essere rimpiazzati da "è".

[domx]

uhm, mi sa che se ci sarà un esercizio simile giovedì non lo farò, magari le spiegazioni le capisco pure, ma non riesco ancora ad arrivarci da solo...

[LukasEta]

uhm, mi sa che se ci sarà un esercizio simile giovedì non lo farò, magari le spiegazioni le capisco pure, ma non riesco ancora ad arrivarci da solo...

Guarda, non ti fare demoralizzare Cioè, non è necessario che per rispondere a un quesito a risposta multipla tu abbia trovato una soluzione bellissima tipo quelle che molti utenti di questo forum riescono splendidamente a dare Spesso basta avere colpo d'occhio, intuire che alcune tra le risposte possibili non sono possibili... basta che te la cavi insomma anche se apparentemente c'è qualcosa che non hai mai visto, devi provarci senza demoralizzarti in partenza. E' una gara di matematica, a ogni cosa ci si può arrivare in tantissimi modi diversi, uno tra questi di sicuro lo puoi trovare con le tue forze Forza coraggio e sangue freddo

[domx]

uhm, mi sa che se ci sarà un esercizio simile giovedì non lo farò, magari le spiegazioni le capisco pure, ma non riesco ancora ad arrivarci da solo...

Guarda, non ti fare demoralizzare Cioè, non è necessario che per rispondere a un quesito a risposta multipla tu abbia trovato una soluzione bellissima tipo quelle che molti utenti di questo forum riescono splendidamente a dare Spesso basta avere colpo d'occhio, intuire che alcune tra le risposte possibili non sono possibili... basta che te la cavi insomma anche se apparentemente c'è qualcosa che non hai mai visto, devi provarci senza demoralizzarti in partenza. E' una gara di matematica, a ogni cosa ci si può arrivare in tantissimi modi diversi, uno tra questi di sicuro lo puoi trovare con le tue forze Forza coraggio e sangue freddo

grazie, molti ultimamente mi stanno dando incoraggiamenti e consigli di questo tipo, speriamo bene...

[fph]

Quest'ultima congruenza mi dice che per x=16, otterrò sempre resto 0, il che ci piace. Però anche $ b^4 $ , se fosse divisibile per x, renderebbe la congruenza sempre verificata => ecco che entra in gioco il fatto che il testo ci dice che i due numeri sono primi tra loro .
Infatti nel caso in cui fosse $ b \equiv 0 \mod x $ , tornando al numero $ a-b $ e sostituendo, otterrei $ a-0 \equiv 0 \mod x $, da cui $ a \equiv 0 \mod x $

Occhio: ti stai perdendo per strada i casi in cui $x \mid b^4$, ma $x \nmid b$, per esempio $x=8$, $b=42$.

[LukasEta]

Occhio: ti stai perdendo per strada i casi in cui x∣b4, ma x∤b, per esempio x=8, b=42.

Eh sì, hai ragione
Provandoci un po' non mi viene come dimostrarli quei casi...come si fa?

[fph]

Hai dimostrato che $x\mid 16b^4$, e nello stesso modo puoi ottenere $x \mid 16a^4$. Ora ti resta da usare l'ipotesi che $a$ e $b$ sono primi tra loro...