Problema Staffetta #5

[Anonimo_Gaussiano]

Dati due numeri a e b, strettamente maggiori di 1. Sappiamo che a²+b e b²+a sono numeri primi.
Dimostriamo che il massimo comun divisore tra ab+1 e a+b vale 1.

[loryyy_]

Ciao! Pubblico la mia soluzione.

Testo nascosto:

Sia [math]a^2+b = p, ove p è un numero primo.
Otteniamo innanzitutto
[math]d := MCD(ab+1,a+b) = MCD(ab+1 - (a+b), a+b) = MCD(ab-a-b+1,a+b) = MCD((a-1)(b-1),a+b)

Supponiamo ora per assurdo che tale d sia diverso da 1.

Allora [math]\exists q \geq 2 numero primo tale che [math]q | d e dunque, per definizione di MCD,
[math]q | (a-1)(b-1), q | a+b

Poiché q è primo [math]q | a-1 oppure [math]q | b-1. Per simmetria mostriamo che se [math]q|a-1 otteniamo una contraddizione, e per l'altro caso è analogo.
Allora
[math]q | a+b

[math]q | (a+b)^2 = a^2+b^2+2ab = (p-b) + b^2+2ab = p + b(b+2a-1) = p +b(a+b) + b(a-1)

Ma dalle condizioni trovate prima sul fatto che q divide sia [math]a+b che [math]a-1, allora q deve dividere il termine restante p.
[math]q | p
Ma allora se entrambi sono numeri primi, l'unica possibilità è che q = p.
Ciò significa che [math]p = q | a+b, dalla condizione di prima su q ma allora

[math]a^2+b \leq a+b

Che implicherebbe [math]a^2 \leq a, ossia negli interi positivi a=1, ma il testo dice che a >1, il che è una contraddizione.

[dario21]

Ecco la mia soluzione.

Testo nascosto:

Inanzitutto notiamo che , detti [math]p=a^2+b e [math]q=b^2+a, se [math]p|a o [math]p|b allora chiaramente [math]a^2+b \ge p^2+p > p che è chiaramente assurdo. Analogamente se valesse [math]p|a+b, si avrebbe [math]p \le a+b <a^2+b=p che è a sua volta assurdo. Perciò detto [math]g=MCD(a+b,ab+1) chiaramente nè [math]p nè [math]q dividono [math]g.

Notiamo ora che :
[math](a^2+b)(b^2+a)=(ab)^2+a^3+b^3+ab=ab(ab+1)+(a+b)(a^2-ab+b^2)=pq, e perciò chiaramente [math]g|(ab)^2+a^3+b^3+ab=ab(ab+1)+(a+b)(a^2-ab+b^2)=pq. Ma poichè [math]p e [math]q sono primi, le uniche possibilità per [math]g sono :

• [math]g=p
• [math]g=q
• [math]g=pq
• [math]g=1

Di queste, le prime 3 possiblità implicano che [math]g sia divisibile per almeno uno tra [math]p e [math]q, che è assurdo per quanto detto all'inizio. Da ciò segue necessariamente [math]g=1.

Testo nascosto:

[emmeci]

Do anche una terza soluzione.

Testo nascosto:

Posto [math]A=(a^2+b)(b^2+a), calcolo
[math]A=a^2b^2+a^3+b^3+ab =ab(ab+1)+(a+b)(a^2-ab+b^2)
Ragiono ora per assurdo: se [math]a+b, ab+1 hanno in comune un divisore [math]x \ne 1, il calcolo mostra che x divide anche A e che [math]x<A. Poiché A è il prodotto di due numeri primi, i suoi unici divisori diversi da 1 e minori di A sono questi numeri primi; senza perdita di generalità, deve essere [math]x=a^2+b. Ma x è divisore di [math]a+b e quìndi gli è minore o uguale; ne segue
[math]a^2+b \le a+b \to a^2-a \le 0 \to 0 \le a \le 1
in contrasto con l'ipotesi a>1.