Euler-Fermat theorem violating division algorithm

Question

Does Euler Fermat theorem not violates the division algorithm?E.g The remainder when 3^47 is divided by 23 is 27. Here remainder exceeds the divisor that is violating the division algorithm.

Answer 1

The remainder when $3^{47}$ is divided by $23$ is not $27$, it is $4$, and Fermat's little theorem does not say otherwise. You are presumably misinterpreting the meaning of the congruence $a\equiv b\bmod n$. This does not mean "the remainder when $a$ is divided by $n$ is $b$." That is not what it means. It is true that if $r$ is the remainder of $a$ dividied by $n$ then $a\equiv r\bmod n$, but the converse does not hold.

Instead, $a\equiv b\bmod n$ is equivalent to $a$ and $b$ having the same remainder upon division by $n$, or equivalently that $(a-b)$ is divisible by $n$. So for example, we can have $50\equiv27\bmod 23$ even though both of $50$ and $27$ are bigger than $23$.