Indukcijom ili mozda ne?

Evo finog zadatka:

Dokazati da se svaki prirodan broj veci od 6 moze predstaviti kao zbir dva uzajamno prosta broja (oba razlicita od 1)

Mozda neko ima drugu ideju osim indukcije, jer ovako ne uspevam da dovrsim zadatak.

Tri slucaja:
- n neparan: n = 2k + 1 = (k + 1) + k, naravno da je (k + 1, k) = 1.
- n paran po modulu 4 je 0: n = 4k = (2k + 1) + (2k - 1) i naravno (2k + 1, 2k - 1) = (2k - 1, 2) = 1.
- n paran po modulu 4 je 2: n = 4k + 2 = (2k - 1) + (2k + 3) i naravno (2k - 1, 2k + 3) = (2k - 1, 4) = 1.
Zbog n > 6, to su svi brojevi veci od 1.
Q.E.D.

Ovo ide preko Ojlerove grupe (odnosno, bar je na Algebri I tako zamišljeno), u svakom slučaju, Anđelićka je to radila na vežbama:

Neka je .

Dokažimo . Pretpostavimo da je:



Tada je:



Iz i i sledi , što je kontradikcija, pa je .

Dokaz za je analogan ovome.

Kako je za svako (što se opet posebno dokazuje, veoma lako), to znači da se svaki broj veći od 6 može predstaviti kao zbir dva uzajamno prosta broja, i to i .