Observam ca 3n+1=M3+1, iar 9n*9n+6=M3, deoarece 3 | 9n*9n si 3 | 6, deci 3 divide si suma lor.
Presupunem ca exista d≠1 un divizor comun al celor doua numere, deci:
d | M3+1
d | M3 si scazand cele doua relatii gasim:
d | 1, adica d=1 Contradictie, deoarece am presupus ca d≠1.
Deci numerele sunt prime intre ele.
