ONE
    Númas
    ← Back to the programme
    OlympiadHardNumber Theory10–12

    Euler's Theorem

    Teorema de Euler

    Find the last two digits of 310003^{1000}.

    Work modulo 100. Use Euler's theorem: if gcd⁡(a,n)=1\gcd(a,n)=1, then aφ(n)≡1(modn)a^{\varphi(n)} \equiv 1 \pmod{n}.

    Solution

    Step 1 of 6

    1. 1.gcd⁡(3,100)=1\gcd(3, 100) = 1, so Euler's theorem applies.