How come any number $m$ that is not a multiple of the primes $p$ or $q$, when raised to the power $(p-1)(q-1)$ and divided by $pq$, always has the remainder $1/(pq)$?
I'm trying to understand it in a simple way. For example:
$p = 3$, $q = 5$ ($p$ can't be the same as $q$, why?)
$m \neq 3k \text{ or }5k$
Let's say we pick $m = 2$.
$$2^{(3-1)(5-1)} / (3\cdot5) = 256 / 15 = 17 + 1/15$$
You mention Euler's theorem in the title of the question; maybe you're not familiar entirely with what it says, but it gives exactly what you're looking for (Wikipedia article).
Euler's theorem: For any natural number $m$ and integer $a$ with $\gcd(a,m)=1$, $a^{\varphi(m)}\equiv 1\bmod m$.
When $m=pq$ for distinct prime numbers $p$ and $q$, we have $\varphi(m)=\varphi(pq)=(p-1)(q-1)$, and also $\gcd(a,m)=\gcd(a,pq)=1$ is true precisely when $a$ is not a multiple of either $p$ or $q$.
Euler's theorem works perfectly well when $m$ is not a product of distinct primes, but the totient function $\varphi$ just acts differently. For example, if $m=p^2$ for some prime $p$ (i.e., a product of primes that are not distinct), then $\varphi(m)=\varphi(p^2)=p(p-1)$, and the result is that for integers $a$ with $\gcd(a,m)=\gcd(a,p^2)=1$, we have $a^{p(p-1)}\equiv 1\bmod p^2$.
Given distinct primes $p,q$, consider the group $G=(\mathbb{Z}/pq\mathbb{Z})^\star$ of invertible elements of the ring $(\mathbb{Z}/pq\mathbb{Z},+,\times)$.
We know that $\mathrm{card}(G)=\varphi(pq)=(p-1)(q-1)$.
Hence, for all $x\in G$ : $x^{(p-1)(q-1)}=\bar{1}$
($\bar k$ denotes the congruence class of the integer $k$, mod. $pq$).
Finally, if $m\in\mathbb{N}$ is coprime to $pq$, then $\bar m\in G$ and we get the desired result.
Lagrange's theorem: When $G$ is a finite group with $n$ members and $H$ is a subgroup of $G$, the number of members of $H$ is a divisor of $n$.
Corollary: $x^n=1$ for each $x\in G,$ where $1$ is the identity element of $ G.$
Because:
(i). $\{x^m: m\in \mathbb N\}$ is finite, so there are $m,m'\in \mathbb N$ with $m<m'$ and $x^m=x^{m'},$ so $x^{m'-m}=1$ with $m'-m\in \mathbb N.$
(ii). Therefore there exists $m''=\min \{ j\in \mathbb N: x^j=1\}$. Then $\{x^j:1\leq j\leq m''\}$ is a subgroup of $G.$ It has exactly $m''$ members, for if $x^a=x^b$ for $1\leq a<b\leq m''$ then $x^{b-a}=1$ with $m''>b-a\in \mathbb N,$ contrary to the def'n of $m''.$
(iii). So by Lagrange's theorem, $m''|n.$ Since $x^{m''}=1$ and $m''|n$ we have $x^n=1.$
$(\bullet )$. As a particular case let $G$ be the members of $\mathbb N$ from $1$ to $pq-1$ that are not divisible by $p$ nor by $q$, with multiplication modulo $pq.$ By a particular case of the Chinee Remainder Theorem, $G$ is a group. Observe that $G$ has $(p-1)(q-1)$ members.
To prove Lagrange's theorem: Let $m$ be the number of members of $H.$ For $x\in G$ define $xH=\{xy:y\in H\}.$
Now prove (i): For $x,x'\in G,$ either $xH=x'H$ or $(xH)\cap (x'H)$ is empty. And prove (ii): For $x\in G,$ the sets $H$ and $xH$ have the same number $(m)$ of members. Therefore $\{xH: x\in G\}$ is a partition of all of $G$ into a pairwise-disjoint family of subsets, each with $m$ members. So $m|n.$
