Problema sul Massimo Comune Divisore

[Francio991]

Buongiorno a tutti, vorrei un aiuto sul seguente problema.

Dimostrare che la frazione $(21n + 4)/(14n+3)$ è irriducibile

Si può osservare che la frazione è irriducibile se $MCD( 21n + 4, 14n+3)=1$. Inoltre si può utilizzare la proprietà per cui $MCD(a,b) = MCD(a, a-b)$. Dunque $MCD( 21n + 4, 14n+3)=MCD(21n + 4, 7n+1)$. A questo punto la soluzione dell'esercizio non mi è più chiara. Vi allego il passaggio che ho trovato nella soluzione:
$d = MCD(21n+4, 14n+3) = MCD(21n+4, 7n+1) = MCD(21n+4, 1) = 1$

Perché $MCD(21n+4, 7n+1) = MCD(21n+4, 1)$ ? Grazie mille in anticipo

[axpgn]

Penso perché $3*(7n+1)=21n+3$

[Francio991]

Scusami, ma continuo a non capire.. $ MCD(3(7n+1)+1, 7n+1)=1$ ? Ed eventualmente perché?

[axpgn]

Vado a braccio … vediamo cosa ne esce ...

Posto $7n+1=a$ abbiamo $\text(MCD)(ka+1,a)=r$ con $k in NN$

Ora proprio per la proprietà che hai detto avremo

$\text(MCD)(ka+1,a)=\text(MCD)(ka+1-a,a)=\text(MCD)((k-1)a+1,a)$

Questo giochetto lo puoi ripetere ma non all'infinito, in quanto essendo $k in NN$ avremo un minimo, perciò prima o poi si arriverà a $k=1$ da cui $\text(MCD)(a+1,a)=1$

Mi pare funzioni, che ne dici?

Cordialmente, Alex

[dan952]

L'algoritmo di Euclide...

[Francio991]

"axpgn":Vado a braccio … vediamo cosa ne esce ...

Posto $7n+1=a$ abbiamo $\text(MCD)(ka+1,a)=r$ con $k in NN$

Ora proprio per la proprietà che hai detto avremo

$\text(MCD)(ka+1,a)=\text(MCD)(ka+1-a,a)=\text(MCD)((k-1)a+1,a)$

Questo giochetto lo puoi ripetere ma non all'infinito, in quanto essendo $k in NN$ avremo un minimo, perciò prima o poi si arriverà a $k=1$ da cui $\text(MCD)(a+1,a)=1$

Mi pare funzioni, che ne dici?

Cordialmente, Alex

Grazie! Adesso è molto più chiaro

[rockthenight]

Ciao,un mio allievo ha dato la seguente soluzione:sia k fattore comune al numeratore e denominatore;allora:
21n+4=0(MOD K)
14n+3=0(MOD K)

ossia:
42n+8=0(MOD K)
42n+9=0 (MOD K)
sottraendo membro a membro:
1=0 (MOD K)
perciò irriducibile