Préparer sa kholle : Arithmétique

On va commencer par étudier les puissances de $3$ modulo $13$. On commence par remarquer que $$3^1\equiv 3\ [13],\quad 3^2\equiv 9\ [13],\ 3^3\equiv 1\ [13].$$ On sait donc que, puisque $126=3*42$, $3^{126}\equiv (3^3)^{42}\ [13]$, et donc $3^{126}\equiv 1\ [13]$. De même, on a $$5^1\equiv 5\ [13],\quad 5^2\equiv 12\ [13],\quad 5^3\equiv 8\ [13],\quad 5^4\equiv 1[13].$$ Par un raisonnement similaire, et utilisant que $126=31*4+2$, on trouve $$5^{126}\equiv 5^2\ [13]\textrm{ soit }5^{126}\equiv 12\ [13].$$ On en déduit que $$3^{126}+5^{126}\equiv 0\ [13],$$ ce qui signifie bien que $13$ divise $3^{126}+5^{126}$.