Show $m$ divides $a_i b_i -a_j b_j$ where ${a_i}, {b_i}$ are permutations of $1,2,...,m$ Let $a_1, a_2,\dots,a_m$ and $b_1,b_2,\dots,b_m$ be any two permutations of $1,2,\dots,m$. Show that if $m>1$ is a prime, then there exist $i$ and $j$ with $i \neq j$ such that $m \mid (a_ib_i-a_jb_j)$. Prove the same assertion if $m$ is composite.
I'm a bit lost as to how I should approach this question since this is my first number theory course. I can't think of a straightforward application of any of the theorems I've covered so far (Fermat, Euler, Wilson, etc). Any suggestions on how I can started?
Also, how can $m$ be a composite if it is prime? Am I misinterpreting something?
Edit: Based on the comment from @runway44, I understand what the latter half of the question is asking. I think the way to deal with composite $m$ is to do a prime factorization: $m=p_1^{\alpha_1}\cdots p_n^{\alpha_n}$ and each $p_k$ divides some $(a_ib_i-a_jb_j)$ for permutations involving $1,\dots, p_k$.
 A: Your claim is not true when $m =2$, it is true when $m \geq 3$.
There are two cases to consider;
$\textbf{Case 1)}$ $m$ is prime, $m = p \geq 3$.
If $a_{1}b_{1},...,a_{p}b_{p}$ are not all distinct modulo $p$ then we have your assertion, if not then we can rearrange this list of moduli so that $a_{j}b_{j} \equiv j \mod p$. Thus for $1 \leq j \leq p-1$ we must have $b_{j} \equiv j a_{j}^{-1} \mod p$. Note that $b_{1},...,b_{p-1} \mod p$ and $a_{1}^{-1},...,a_{p-1}^{-1} \mod p$ is a rearrangement of the list $1,2,...,p-1 \mod p$. Thus we must have $b_{1}...b_{p-1} \equiv (p-1)! \equiv -1 \mod p$. But
$$\prod_{j=1}^{p-1}b_{j} \equiv \prod_{j=1}^{p-1} j a_{j}^{-1} \equiv ((p-1)!)^{2} \equiv 1 \mod p$$
Since $-1 \not \equiv 1 \mod p$ for $p \geq 3$ this is impossible. Thus we have proof for this case.
$\textbf{Case 2)}$ $m$ is composite, $m \geq 3$.
If $a_{1}b_{1},...,a_{m}b_{m}$ are not all distinct modulo $p$ then we have your assertion, if not then we can rearrange this list of moduli so that $a_{j}b_{j} \equiv j \mod m$. Let $1=d_{1} < d_{2} <...< d_{k}= m$ be all the distinct divisors of $m$. Set $$G(h,m) = \left[r: 1\leq r \leq m, \gcd(r,m) = h\right]$$
$$A(h,m) = \left[a_{r}: 1\leq r \leq m, \gcd(r,m) = h \right]$$
$$B(h,m) = \left[b_{r}: 1\leq r \leq m, \gcd(r,m) = h \right]$$
(Observe that we used list notation, not set notation, the list is arranged from smallest to largest indexed on valid $r$ with the correct gcd). Note that if $gcd(u_{1},m) = 1$ then $\gcd(a_{u_{1}},m) = 1$ and $\gcd(b_{u_{1}},m) = 1$ as $a_{u_{1}}b_{u_{1}} \equiv u_{1} \mod m$. Thus $A(1,m)$ and $B(1,m)$ are a rearrangement of $G(1,m)$. Suppose that $A(d_{j},m)$ and $B(d_{j},m)$ are a rearrangement of $G(d_{j},m)$ for $j = 1,...,h \leq k-1$, note that if $(w,m) = d_{h+1}$ then $a_{w}$ or $b_{w}$ cannot be from $G(c,m)$ where $c \leq d_{h}$ and cannot be from $G(d_{s},m)$ where $s \geq h+2$ (if $h+2 \leq k$) as $a_{w}b_{w} \equiv w \mod m$. Thus $a_{w}$ and $b_{w}$ belong to the list $G(d_{h+1},m)$, thus we have that $A(d_{h+1},m)$ and $B(d_{h+1},m)$ are a rearrangement of $G(d_{h+1},m)$.
The above argument shows that $(a_{w},m) = (b_{w},m) = (w,m)$. This situation would be impossible if $m$ had a non-trivial square factor; if $q^2 |m$ where $q > 1$ then  $a_{q}b_{q} \equiv \alpha q^2 \mod m$ (for some $\alpha \in \mathbb{N}$) and $a_{q}b_{q} \equiv q \mod m$, the two modular equations contradict one another.
For $m$ square free and $m \geq 3$, $m$ has an odd prime factor $z$. With the above arrangement, $A(\frac{m}{z}, m)$ and $B(\frac{m}{z},m)$ consist of numbers which are multiples of $\frac{m}{z}$ and each numbers in the respective list are distinct modulo $z$. We may pass this situation to case $1$ so that we may find numbers $1\leq u < v \leq z$ so that $a_{\frac{m}{z}u}b_{\frac{m}{z}u} - a_{\frac{m}{z}v}b_{\frac{m}{z}v} \equiv 0 \mod z$. Certainly we also have $a_{\frac{m}{z}u}b_{\frac{m}{z}u} - a_{\frac{m}{z}v}b_{\frac{m}{z}v} \equiv 0 \mod \frac{m}{z}$. By the Chinese remainder theorem, as $(\frac{m}{z},z) = 1$, we have $a_{\frac{m}{z}u}b_{\frac{m}{z}u} - a_{\frac{m}{z}v}b_{\frac{m}{z}v} \equiv 0 \mod m$, which would be a violation of our arrangement.
A: This is just the product of my effort to deciper @acreativename's excellent answer.
When $m=p>2$ is a prime, this boils down to the Wilson's theorem: If $a_ib_i$ is a full list of $\{1, \cdots, p-1, p\}$, by rearrangement, we may assume $a_ib_i\equiv i\mod p$. Note that when $i\not=p$, $p\not\mid i$, hence $p\not\mid a_i, b_i$, and therefore $\{a_1, \cdots, a_{p-1}\}$ and $\{b_1, \cdots, b_{p-1}\}$
Now we have $(p-1)!=\prod_{i=1}^{p-1}a_ib_i=\prod_i a_i\prod_i b_i = (p-1)!^2$, but $(p-1)!\equiv-1\mod p$, hence $-1\equiv 1\mod p$, a contradiction.
This is essentially the same as @acreativename's answer, but we don't have to take inverses.
When $m$ is not a prime, consider a prime $p\mid m$, note that $p\not\mid a_ib_i$ iff $p\not\mid a_i$ and $p\not\mid b_i$, but the number $\{1\le n\le m|p\not\mid n\}$ is fixed and finite, hence after deleting those equations with $p\not\mid a_ib_i$, we must have $p\mid a_ib_i$ iff $p\mid a_i$ and $p\mid b_i$.
If $p^2\mid m$, consider the equation $a_ib_i\equiv p\mod m$, which implies $a_ib_i\equiv p\mod p^2$, but since $p\mid a_i$ and $p\mid b_i$, we have $p^2\mid a_ib_i$, hence $0\equiv p\mod p^2$, a contradiction.
This shows that as long as $m$ is not square-free, we are done. Now assume $m$ is square-free, consider $p\mid m$ and all the equations $a_ib_i=c_i$ with $p|a_i$ and $p|a_i$, that is $pa_i'pb_i' \equiv pc_i' \mod m$ where $a_i', b_i', c_i'$ all form a full list of $\{1, \cdots, m/p\}$ separately. Thus $p(a_i'b_i')\equiv c_i'\mod m/p$, since $p\not\mid m/p$, $p\mod m/p$ is invertible, hence $a_i'b_i'\equiv p^{-1}c_i'\mod m/p$ also form the full list of residues mod $m/p$. Since $m$ is not prime and square free, we may pick $p=2$ when $m$ is even and any prime factor $p$ when $m$ is odd, such that $m/p$ still has an odd prime factor. Now inductively we can keep reducimg the number of prime factors of $m$, until it's just an odd prime to get a contradiction.
