Determine the least non-negative residue $x$ of the following congruences:
(a) $7^{101} ≡ x \pmod {11}$
(b) $2^{1976} ≡ x \pmod {13}$
(c) $5^{1961} ≡ x \pmod {7}$
(d) $3^{2013} ≡ x \pmod {23}$
(e) $26^{2013} ≡ x \pmod {23}$
We remind ourselves of Fermat's Little Theorem (FlT). For integer $a$ and prime $p$, where $p \not \mid a$, we have
$$ a^{p-1} \equiv 1 \pmod {p} $$
(a) Since 11 is prime, and doesn't divide 7, we can use the FlT.
$ 7^{10} \equiv 1 \pmod {11} $
$ (7^{10})^{10} \equiv 1^{10} \pmod {11} $
$ 7^{100} \equiv 1 \pmod {11} $
$ 7^{100} \times 7 \equiv 7 \pmod {11} $
$ 7^{101} \equiv 7 \pmod {11} $
(b) Since 13 is prime, and doesn't divide 2. we can use the FlT.
$ 2^{12} \equiv 1 \pmod{13} $
$ (2^{12})^{164} \equiv 1 \pmod{13} $
$ 2^{1968} \times 2^8 \equiv 256 \equiv 9 \pmod{13} $
$ 2^{1976} \equiv 9 \pmod {13} $
(c) Since 7 is prime, and doesn't divide 5, we can use the FlT.
$ 5^{6} \equiv 1 \pmod 7 $
$ (5^{6})^{326} \equiv 1 \pmod 7 $
$ 5^{1956} \times 5^5 \equiv 3125 \equiv 3 \pmod 7 $
$ 5^{1961} \equiv 3 \pmod 7 $
(d) Since 23 is prime, and doesn't divide 3, we can use the FlT.
$ 3^{22} \equiv 1 \pmod {23} $
$ (3^{22})^{91} \equiv 1 \pmod {23} $
$ 3^{2002} \times 3^{11} \equiv 177147 \equiv 1 \pmod {23} $
$ 3^{2013} \equiv 1 \pmod {23} $
(d) We first note that
$ 26 \equiv 3 \pmod {23} $
$ 26^{2013} \equiv 3^{2013} \equiv 1 \pmod {23} $ using (d) above.