WisFaq!

Module rekenen en bewijzen

Ik heb de volgende vraag. Ergens las ik dat je kunt bewijzen:

Als p en q verschillende priemgetallen zijn dan geldt:
p^q+q^pºp+q(mod pq).

Hoe moet ik dit bewijzen??

Groetjes

van de Velde
4-1-2004

Antwoord

Hoi,

De kleine stelling van Fermat leert dat a^p-1=1 (mod p) wanneer ggd(a,p)=1.

In het bijzonder zal je voor 2 verschillende priemgetallen p en q dus hebben dat: q^p-1=1 (mod p) en p^q-1=1 (mod q).

Dus is q^p-1-1=p.n en p^q-1-1=q.m voor gehele n en m.
Zodat: q.(q^p-1-1)=q.p.n en p.(p^q-1-1)=p.q.m.
Optellen levert dan: q^p-q+p^q-q=p.q.(n+m). Hieruit volgt dan onmiddellijk het te bewijzen.

Groetjes,
Johan

andros
4-1-2004