You are right, the proof is actually very simple:
If m1 | (a-r) and m2 | (a-r) then a-r is a common multiple of m1 and m2. Therefore it is divisible by the least common multiple, [m1, m2]. Thus [m1, m2] | (a-r), or a \equiv r (mod [m1, m2])
Why "modulo m1" and "modulo m2" implies "modulo [m1, m2]"
If a \equiv r (mod m1) and a \equiv r (mod m2) then a \equiv r (mod [m1, m2]), where [a, b] is the least common multiple of a and b.
I have tried to prove that.
Assume that
[m_{1}, m_{2}] = l_{1}m_{1} = l_{2}m_{2}
and
a =...
There is a way how to prove it using just the definition:
If x is prime to n, then also n - x is prime to n (easily proven by contradiction). Except for the case when x = n/2, x and n - x are distinct. But when x = n/2, then n/x = 2 and x is not prime to n. So the numbers which are primes to...
I know it's a dumb question but I can't figure out why the totient of n is always even (I've read in a book that it "follows immediately from the definition of the totient function", so it should not require any theorem to prove). It is clear to me that it holds true for
n = pk, where p is a...