Trick of Mind

7 Responds so far- Add one»

1. 1. Chris Said：
   May 23rd, 2012 at 4:17 pm

   GCD and LCM

   Any number, d, that satisfies d|a and d|b is a called a common divisor of a and b.
   The greatest possible value of d is denoted as gcd(a,b). It immediately follows that gcd(fa,fb) = f gcd(a,b). If a’ and b’ have no common factor, then gcd(a’,b’) = 1. Let a = a’g and b = b’g, then gcd(a,b) = gcd(a’g,b’g) = g gcd(a’,b’) = g. Every common divisor of a and b must be a factor of g.

   Any number m that satisfies a|m and b|m is called a common multiple of a and b. The lowest possible value of m is denoted as lcm(a,b). It immediately follows that lcm(fa,fb) = f lcm(a,b). If a’ and b’ have no factors in common, we must have that lcm(a’,b’) = a’b’. So lcm(a,b) = lcm(a’g,b’g) = g lcm(a’,b’) = ga’b’ = ab/g. So
   lcm(a,b) gcd(a,b) = ab. Every common multiple of a’ and b’ must be a multiple of a’b', so every common multiple of a and b must a multiple of lcm(a,b).

   The generalisation of gcd and lcm to more than two integers isn’t so nice.

   Here’s an important property of gcd’s (I’m using the notations and definitions from above): Consider gcd(a+ub,b). Now a’+ub’ cannot be divisible by any factor of b’, so gcd(a’+ub’,b’) = 1. But gcd(a+ub,b) = gcd((a’+ub’)g, b’g) = g gcd(a’+ub’,b’) = g. i.e. gcd(a+ub,b) = gcd(a,b). It also follows that gcd(a,b+va) = gcd(a,b). I’ll use this in the modulo arithmetic post (later).
2. 2. Chris Said：
   July 22nd, 2012 at 12:10 pm

   The fundamental theorem of arithmetic (TFTOA).
   aka the unique prime factorisation theorem.

   All integers are divisibe by 1 and itself; I shall call such divisors, trivial divisors.
   Integers > 1 that only have trivial divisors are called primes. The non-primes > 1 are called composites.

   Lemma: all integers > 1 are either prime or may be written as a composite formed by multiplying primes together.

   Proof: We check all integers less than n and find the statement to be true (we can stop at n = 3). Consider n, if it’s a prime, we’re done. If not, we will have an a and b such that n = ab, where 1 < a,b < n, and so we know a,b have prime representations, and so we replace a and b with those representations and write n = ab as a product of primes. Now rinse and repeat, QED.

   If gcd(a,b) = 1, then a and b are said to be coprime (or relatively prime), and that simply means they have no primes in common. Because 1 is not a prime (and so has no prime factors), it is coprime to every integer, so for any integer a, gcd(a,1) = 1.

   —-
   Euclid’s lemma: if p is prime and a and b are integers and if p|ab, then at least one of p|a or p|b is true.

   Proof: If p|a then we’re done. If not, then we note that as a|ab and p|ab (by
   assumption) that ab is a common multiple of a and p. Therefore lcm(a,p)|ab.
   But lcm(a,p) gcd(a,p) = ap. As p¦a, we have gcd(a,p) = 1 and so
   lcm(a,p) = ap. So ap|ab, and removing the a factors => p|b, QED.

   We can use the lemma to generate a corollary: If p|abcd…, then at least
   one of p|a, p|b, p|c, p|d … is true. WLOG, if we assume that p doesn’t divide a,
   then by substituting B = bcd…, then we have p|aB, so we must have p|B, etc.

   Another extension to Euclid’s lemma is that if n is composite and gcd(a,n) = 1,
   and n|ab then n|b. Some authors say that this extension is actually Euclid’s lemma. The proof is almost identical to the previous one.

   We may now prove the fundamental theorem of arithmetic: Every integer > 1
   is defined by a unique product of primes. Trivially, a prime is simply itself.

   Proof: Assume the contrary, and there is a lowest N which has more than one prime representation. i.e. N = p₁ p₂ … p_m = q₁ q₂ … q_n.
   The p’s and q’s aren’t necessarily unique (in the given representation) e.g. I’d write 8 = 2*2*2 rather than 2³. As N is the lowest integer with that property, no p can equal a q (otherwise we could divide them out and obtain a lower value for N).

   Now p₁|N, so p₁|q₁ q₂ … q_n. But by the corollary to Euclid’s lemma, p₁ must divide at least one of the q’s. But the q’s are primes, and can only be divided by themselves, so one of the q’s must in fact be p₁. That contradicts the initial assumption, which therefore is false, QED.

   New proof of TFTOA: Assume that we’ve verified a weak version of TFTOA, the WFT, that’s true for all integers < N. If we can then show that the WFT is also true for N, then the WFT becomes TFTOA (by infinite ascent). Assume (falsely) that the WFT fails at N, so N is the least integer that has more than one prime representation and so we may write, N = pP = qQ, where p and q are the least primes in each representation, and P and Q represent the remaining primes. No prime is common to both sides (otherwise the WFT would have failed earlier). As P,Q < N, using the WFT, q¦P and p¦Q. As p and q are the smallest prime factors, p,q ≤ √N. Both cannot take on the equality (otherwise we’d get p = P = q = Q) and so pq < N. Similarly, it folllows that P,Q ≥ √N. Both cannot take on the equality and hence P > q (and Q > p).

   Any integer n may be written in terms of a “fixed” integer m i.e. n = am + b.
   If we also stipulate that 0 ≤ b < m, then a and b are uniquely defined. Further, if n is not a multiple of m, then b ≠ 0 – I’ll take it that all that is pretty obvious and doesn’t require the WFT (or TFTOA) to establish it.

   So we may write P = aq + b. As P > q, and q¦P, we have 0 < b < q < P < N. So N = pP = p(aq + b) => N/q = Q = p(a + b/q) = pa + pb/q. Q and pa are integers, so we need pb/q to be an integer. Now, pb < pP (from the previous inequalities) so pb < N (as pP = N) => pb has a unique prime representation and so by the WFT, q is coprime to both p and b (as b < q), so pb/q cannot be an integer. So the WFT cannot fail at N and TFTOA is true.
   —
   As an example of the power of TFTOA, I’ll use it to prove that if n is an integer then √n is rational (in fact integral) IFF n is a perfect square.

   Proof: If n is a perfect square then, trivially, √n is integral. If not, let √n = u/v,
   where u and v are the smallest integers that satisfy, i.e. gcd(u,v) = 1. Squaring
   => n = u² /v² => n v² = u². n, u and v have a unique prime representation. As
   u and v have no common factors and n cannot cancel out v², we must have
   v² = 1. That leaves us with n = u². QED

   That can immediately be generalised to the r th root case.
3. 3. Chris Said：
   July 23rd, 2012 at 5:54 pm

   Modulo arithmetic

   Any integer, n, can be written n = qm + r. So n = r (mod m)

   To avoid excessive specification, it is usually assumed that 0 ≤ r < m,
   but that isn’t a requirement. In fact it is also quite common to write r as a
   negative value e.g. 9 = -1 (mod 10)

   It is a common convention to write (mod m) at the end of a set of chained
   statements, and then it is taken to apply to the entire chain.
   e.g. x = 23 = 13 = 3 (mod 10)

   Addition: n₁ + n₂ = (mq₁ + r₁) + (mq₂ + r₂)
   = m(q₁ + q₂) + (r₁ + r₂) = r₁ + r₂ (mod m)

   Multiplication: n₁ n₂ = (mq₁ + r₁)(mq₂ + r₂)
   = m(mq₁q₂ + q₁r₂ + q₂r₁) + r₁ r₂ = r₁ r₂ (mod m)

   Exponentiation: If a = b (mod m), then aⁿ = bⁿ (mod m)

   Division: Not generally defined.

   Cancellation: if x is coprime to m, i.e. gcd(x,m) = 1, then ax = bx (mod m)
   => a = b (mod m).

   Proof: ax = bx (mod m) => (a – b)x = 0 (mod m). As x has no common factors
   with m, then a-b = 0 (mod m) => a = b (mod m). More formally (I shan’t do this
   every time), we have (a-b)x = 0 (mod m). That is equivalent to m|x(a-b). But
   gcd(m,x) = 1, so by Euclid’s extended lemma, m|(a-b) i.e. a-b = 0 (mod m)
   => a = b (mod m).

   In consequence of these facts, it is broadly the case that if an equation is true, then it is also true in modulo arithmetic.

   If a = b (mod m) then gcd(a,m) = gcd(b,m).
   Proof. In the first post I showed that gcd(a+ub, b) = gcd(a,b).
   a = b (mod m) => a = qm + b. So gcd(a,m) = gcd(qm+b,m) = gcd(b,m), QED.

   It follows that if a is coprime to m, then b is coprime to m (and vice-versa).
   This understanding is essential for the proof of Euler’s theorem (below). This can seen to be related to Bézout’s identity.

   ——
   Fermat’s Little Theorem (FLT): If p is prime and gcd(a,p) = 1, then
   a^p-1 = 1 (mod p)

   Proof: Let S = {a, 2a, 3a, …, (p-1)a}. Each element is distinct, mod p, because if any two were equal, say ia = ja (mod p), then by cancellation, i = j. So the elements of S, mod p, are simply (a permutation) of the integers 1 to p-1. So
   a * 2a * 3a * … * (p-1)a = 1 * 2 * 3 * … * (p-1) (mod p).
   Cancelling the 1,2,3,…,(p-1) literals => a^p-1 = 1 (mod p), QED
   NB Cancellation is allowed as every factor (and so any product of them) is coprime to p.

   ——
   Euler’s Theorem: This is a generalisation of FLT. If gcd(a,m) = 1, where m is prime or composite, then if φ(m) is the number of integers ≤ m that are coprime to m, then a^φ(m) = 1 (mod m)

   Proof: Let S = {r₁, r₂,…, r_φ(m)} where the r_i are the integers ≤ m that are coprime to m. Let aS = {ar₁, ar₂, …, ar_φ(m)}. Each element of aS must be distinct, mod m, because if ar_i = ar_j (mod m), then by cancellation r_i = r_j and that is only possible if
   i = j (by definition of r_i in S). Since each ar_i is relatively prime to m, and there must be φ(m) such integers, it must be that the elements of aS, mod m, are simply a permutation of the elements of S. So
   ar₁ * ar₂ * … * ar_φ(m) = r₁ * r₂ * … * r_φ(m) (mod m).
   Cancelling the r’s => a^φ(m) = 1 (mod m), QED

   ——
   Euler’s Totient Function, φ(m): φ(m) is the number of integers ≤ m that are coprime to m. NB by convention, 1 is coprime to every integer.

   If m = p₁^n₁ * p₂^n₂ * … then φ(m) = m(1 – 1/p₁)(1 – 1/p₂) …, where the p_i are the prime factors of m.

   Proof: All the proofs that I’ve have found have left me unhappy – they are not clear or they appeal to “advanced” mathematics. So I’ve rolled my own.

   First the statutory case – if m = p is prime, then 1, 2, 3, …, p-1 are all coprime to p. So φ(p) = p-1 (and Euler’s theorem reduces to FLT). One way to do that is to proceed by successive approximations. First assume that all p integers ≤ p are coprime to p, then correct that by noing that p isn’t coprime to itself.

   Non-trivial warmup example. If m = p₁p₂p₃, where the p_i are distinct primes. Initially assume that all m integers are coprime to m. Then correct that by noting that there are m/p₁ integers that are divisible by p₁, m/p₂ integers that are divisible by p₂ and m/p₃ integers that are divisible by p₃. So far that means that φ(m) = p₁p₂p₃ – (m/p₁ + m/p₂ + m/p₃). But now we have overcounted the corrections: m/(p₁p₂) of those are divisible by both p₁ and p₂, m/(p₂p₃) are divisible by both p₂ and p₃ and m/(p₃p₁) that are divisible by both p₃ and p₁. But we have again overcounted the corrrections as m/(p₁p₂p₃) (= m/m = 1 in this example) are dvisible by all three of p₁, p₂ and p₃. Allowing for all the corrections => φ(m) =
   m – (m/p₁ + m/p₂ + m/p₃) + (m/(p₁p₂) + m/(p₂p₃) + m/(p₃p₁)) – m/(p₁p₂p₃) and after some jiggling about we get φ(m) = m(1 – 1/p₁)(1- 1/p₂)(1- 1/p₃) as can be verified by simply expanding the latter.

   If there had been N distinct primes, we’d have got
   φ(m) = m – Σm/p_i+ Σm/(p_ip_j) – Σm/(p_ip_jp_k) + … ± Σm/(p_ip_jp_k…p_N)
   = m ∏(1 – 1/p_i), as can be found by expanding the product. NB ∏ means product.

   Note that the various sums are taken over the distinct pairs, triples, etc., of the p_i’s. When we are dealing with the R-ples of the primes at a time, then the number of terms under the sum = C(N,R) = N!/(N! (N-R)!)

   Now to fully generalise. By having used the “trick” of writing the number of factors as m/…, it is immediately obvious that it doesn’t matter if say m = p₁^n₁ p₂ p₃, we’d get the same result.

   That’s pretty well a complete proof. At the time of writing, I thought it was original, but I later discovered the same idea at http://mathworld.wolfram.com/TotientFunction.html (rats!)

   Consider m = pⁿ, we get φ(pⁿ) = pⁿ(1 – 1/p) = p^n-1φ(p)
   If m and n are coprime, it is obvious that φ(mn) = φ(m) φ(n) etc.

   I expect that most (if not all) of the properties of φ() that you can find can now be deduced from the explicit formula.
4. 4. Chris Said：
   July 28th, 2012 at 4:48 am

   The prime number theorem and the infinitude of the primes.

   First some proofs that there are infinitely many primes.

   Initially assume that there are finitely many primes. Let the largest be p.
   Now p! + 1 cannot be divisible by any prime (or indeed any integer ≥ 2 and ≤ p). So there must be another prime > p (and ≤ p! +1) and that contradicts the initial assumption, which therefore is false.

   Here’s Euclid’s proof. Make a list of any n primes, then consider N = p₁p₂…p_n + 1. If N is prime, then it is not in the list of primes. If N is composite, then it has a prime factor that is not in the list. Either way there is a prime not in the list. So for any finite list of primes, there is another prime that isn’t in the list. Therefore there are infinitely many primes.

   PS I fancy that I could rewrite the first proof to avoid contradiction. I wonder how many proofs by contradiction could be rewritten so as to avoid it.
   This is only a brief note. I’m posting it because the derivation of the approximation to the nth prime is glossed over just about everywhere on the Internet.

   If ∏(x) = the number of primes ≤ x, where x is a real number, then
   ∏(x) ~ x/ln(x). A better approximation is ∏(x) ~ x/(ln(x) – 1). There are better approximations, but the first one has the advantage that it is very simple to calculate with. The symbol ~ denotes an aymptotic approximation.
   i.e. as x → ∞, ∏(x)/(x/ln(x)) → 1

   Using that, it is possible to estimate the nth prime as follows. If p_n is the nth prime, then by definition, ∏(p_n) = n. Subsituting p_n for x in the asymptotic equation => n ~ p_n/ln(p_n) and then p_n ~ n ln(p_n). Sadly that isn’t very useful.

   Taking logs of the first form of the expression => ln(n) ~ ln(p_n) – ln(ln(p_n)). But,
   ln(ln(p_n)) << ln(p_n), for large p_n, so ln(n) ~ ln(p_n) and we finally get p_n ~ n ln(n) , and that is useful. In fact we can do better and show p_n ~ n (ln(n) + ln(ln(n)) – 1).

   NB these asymptotic things really make my brain hurt. Although ln(n) ~ ln(p_n) is correct, it does not follow that n ~ p_n.

   The follow lists n, p_n, and the error with the first and second estimators.
   10³, 7919, 12.8%, -11.6%
   10⁶, 15 485 863, 10.8%, -6.2%
   10⁹, 22 801 763 489, 9.1%, -4.2%
   10¹², 29 996 224 275 833, 7.9%, -3.2%

   I did a check for p_n ~ n ln(n) and p_b ~ n (ln(n) + ln(ln(n)) -1) and got:
   10³, -12.8%, -0.99%
   10⁶, -10.8%, -0.29%
   10⁹, -9.1%, -0.21%
   10¹², -7.9%, -0.15%

   See: http://primes.utm.edu/howmany.shtml for some nice info on the prime number theorem. It includes mention on how to get an exact formula (which is 0.5 too low when x is a prime, but is correct everywhere else), using the Riemann zeta function.
5. 5. Chris Said：
   July 28th, 2012 at 1:34 pm

   Bezout’s Identity

   Throughout, I shall assume that a and b are both > 0.
   This simply makes discussion simpler. The extension to negative values is trivial.

   Bezout’s Identity: If a and b are non-zero integers then there exists
   integers u and v such that gcd(a,b) = au + bv

   If gcd(a,b) = 1, then there is a u and a v such that 1 = au + bv.
   I’ll use the latter form. The former form follows trivially from it.
   Typically one of u or v is negative. There are infinitely many u, v pairs
   e.g. au + bv = a(u-b) + b(v+a)

   It is obvious that we can write k = au + bv, where k is some integer.
   If gcd(a.b) > 1, then simply divide the equation by gcd(a,b). I’ll assume that’s
   already done. We need to show that k = 1 is always possible.

   Proof: Now consider an (mod b) for n = 1,2,…,b-1. We’ll get b-1 residues.
   None of them = 0 as a is coprime to b, and n cannot be divisible by b (as
   it’s less than b). The residues are unique by the cancellation law i.e. if x
   and y were such that ax = ay (mod b), then x = y (mod b). So the residues
   must be the set of integers 1,2,…,b-1 and obviously 1 is one of them.
   So there’s an n = u say, such that au = 1 (mod b). But if au = 1 (mod b),
   we immediately have that 1 = au + bv QED

   —
   aaarghh. I just managed to find a different proof that I published ages ago.
   http://trickofmind.com/?p=778#comment-4487
   I went trawling the Internet to find the basis for my version above.

   —–

   Whilst I was writing the above, I noticed the following. Let ax = y (mod m). Fix a, choose a value for x, and calculate y. Now let x = y, and repeat. Keep going until you get the starting x. e.g. with a = 3, m = 10, and x = 1, we y = 3 (mod 10). Then we get 3*3 = 9 (mod 10), then 3*9 = 7 (mod 10) and finally we get 3*7 = 1 (mod 10) and we’re back at the start. By trying all values for x, we find that that there are three loops: 3,9,7,1; 6,8,4,2 and 5.

   Of course what we’re really doing is ax = y (mod m), then a(ax) = y (mod m),
   a(a(ax)) = y (mod m) etc. Altogether we complete the loop when we have
   aⁿx = x (mod m).

   Euler’s theorem says a^φ(m) = 1 (mod m). So n is at most φ(m).
   φ(10) = 10(1 – 1/2)(1 – 1/5) = 4. So that’s why no loop has no more that 4 steps.
   A loop can be shorter. In the example we have two loops of length 4 and one of length 1. For each loop, that gcd(x,m) is the same. That follows, as I showed earlier on this page, that if u = v (mod m), that gcd(u,m) = gcd (v,m). In this case, u = ax and v = y and gcd(a,m) = gcd(3,10) = 1. It follows that gcd(ax,m) = gcd(x,m). In the example, for the first loop, gcd(x,10) = 1. For the second loop gcd(x,10) = 2. For the third loop, gcd(x,10) = 5.

   NB If gcd(a,m) > 1, then the analysis requires more care as gcd(ax,m) ≥ gcd(x,m). If gcd(a,m) ≠ 1, then we can have loops terminating in 0 and loops that do not share a common gcd.

   There can be multiple unit length loops. A unit length loop must satisfy
   ax = x (mod m) => x(a-1) = 0 (mod m). If a-1 has common factors with m,
   then for each common factor, c, there is an x such that cx = m => x = m/c.

   In the example (a = 3, m = 10), we get a-1 = 2, and so x = 10/2 = 5.

   I ‘ve seen enough to know that there are many possible scenarios and that
   there are no really simple rules.
6. 6. Chris Said：
   July 30th, 2012 at 5:32 am

   Quadratic Reciprocity, QR. This theorem is amazing.
   99% of the following only applies to the odd primes.

   Intro. Consider solving, for x, the equation: x² = a (mod p), where p
   is prime and a is coprime to p. Raising both sides to the power (p-1)/2 =>
   x^p-1 = a^(p-1)/2 (mod p)
   Fermat’s little theorem => x^p-1 = 1 (mod p), so we get
   a^(p-1)/2 = 1 (mod p), if the original equation is solvable.

   NB If the equation has a solution x = X, and p is an odd prime then it also has
   the distinct solution x = -X = p-X (mod p).

   Notation. I’ll use a = (b mod m) to imply that the mod only acts on b, and
   produces the integer, a, that is either the least positive residue, LPR, or
   the least absolute residue, LAR. Which one is usually clear by context.
   0 ≤ LPR < m and -m/2 < LAR ≤ m/2
   In the following, I’m choosing the LAR as it produces slicker statements.

   For convenience, define the Legendre symbol, (a/p) = (a^(p-1)/2 mod p).
   We now have that, if the original equation is solvable, then (a/p) = 1.

   But Fermat’s little theorem only guarantees that a^p-1 = 1 (mod p),
   or if you prefer, (a/p)² = 1. But that => (a/p) = ±1.
   It should be clear that if (a/p) = -1, then the original equation is unsolvable.
   What I currently don’t know how to prove is that if (a/p) = 1, then the original
   equation is solvable. So take it on trust that:
   x² = a (mod p) is solvable if and only if (a/p) = 1.

   Aside: there are extensions to QR that work with composite modulo bases. For them, (a/m) = -1 guarantees no solution, but (a/m) = 1 is only necessary, but not sufficient to guarantee that a solution exists. NB when m is not prime (a/m) is the Jacobi symbol or even the Kronecker symbol.

   If (a/p) = 1 then a is said to be a quadratic residue (mod p), otherwise it is a
   quadratic non-residue (mod p).

   NB Knowing that (a/p) = 1, doesn’t tell us how to actually solve the equation.
   None of the above is QR itself – it’s just an introduction. Even QR (which I’m about to define), only helps us to calculate (a/p) and/or place constraints on permissible values of p.

   Quadratic Reciprocity. This is presented as a set of several statements.
   Supplement 0: (1/p) = 1. That’s self-evident, and not usually mentioned.
   In the following, only odd primes are considered.
   Supplement 1: (-1/p) = (-1)^(p-1)/2 = (p mod 4). That’s easy to see.
   Supplement 2: (2/p) = (-1)^{(p^2 -1)/8}. Proof here
   From that, it’s easy to see that =>
   (2/p) = 1 if p = ±1 (mod 8 )
   (2/p) = -1 if p = ±3 (mod 8 )

   QR: (p/q)(q/p) = (-1)^(p-1)(q-1)/4, where p and q are odd primes. Proof here
   This was first proven by Gauss. He wrote eight proofs altogether, and there are over two hundred proofs so far. It is customary to note that
   If (q/p)(p/q) = 1, then both p and q are quadratic residues or non-residues.
   If (q/p)(p/q) = -1, then one of p and q is a quadratic residue and the other
   is a quadratic non-residue.

   By the definitiion, (a/p)(b/p) = (ab/p), and it follows that (a²/p) = (a/p)² = 1.
   Hence, if (q/p)(p/q) = ±1, then (q/p) = ±(p/q) and we may rewrite the
   main equation as (p/q) = (-1)^(p-1)(q-1)/4(q/p)

   For examples of actually using this stuff see:
   http://trickofmind.com/?p=957#comment-7075 and the two posts after that.
7. 7. Chris Said：
   August 4th, 2012 at 4:15 pm

   Wilson’s Theorem. (m-1)! = -1 (mod m) if and only if m is a prime.
   Corollaries: If m = 4, then (m-1)! = 2 (mod 4), this is the only anomolous case. For all other composites, (m-1)! = 0 (mod m), which itself is quite nice.

   Proof: First check for m = 1, 2, 3 and 4
   (1-1)! = 0! = 1 = 0 (mod 1)
   (2-1)! = 1! = 1 = -1 (mod 2)
   (3-1)! = 2! = 2 = -1 (mod 3)
   (4-1)! = 3! = 6 = 2 (mod 4)
   The case for m = 1 (assuming the theorem is true) is consistent with considering 1 to not be prime.

   Consider the list: 2,3,…,m-1. If m is composite (but not the square of a prime), then all of m’s non-trivial divisors are in the list. So (m-1)! is divisible by m.
   If m = p^2, where p is an odd prime, then we will find p and 2p are in the list. So (m-1)! includes p and 2p terms and so is a multiple of m.
   If p = 2 => m = 4, then (p-1)! is not a multiple of m – that is the only anomolous case, and we have (4-1)! = 2 (mod 4).
   So for all composites, except m = 4, (m-1)! = 0 (mod m).

   For m prime, we need to do some more work. Consider the equation
   ab = c (mod m). NB as m is prime gcd(a,m) = gcd(b,m) = gcd(c,m) = 1. If we
   fix a, then let b take on the values 1 to m-1, c will take on all the values in the
   range 1 to m-1. There cannot be two values for b that produce the same c. If
   that were so we’d have ab₁ = ab₂ (mod m) and by
   the cancellation law we’d have b₁ = b₂ (mod m). It
   follows that for each a, there is a b such that ab = 1 (mod m). b is said to be
   the inverse of a (and vice versa). a = 1 and a = m-1 (= -1 (mod m)) are special
   cases as each is its own inverse. No other integers have that property. Proof:
   a^2 = 1 (mod m), prime m, => a^2 -1 = (a-1)(a+1) = 0 (mod m). As m is prime,
   neither a-1 or a+1 can be factors of m, so either a-1 or a+1 = 0 (mod m) =>
   a = ±1 (mod m), i.e. a = 1 or m-1.

   Aside: even if m were composite, a = ±1 (mod m) are solutions, but there may be other solutions as well – I might investigate those in another post. But offhand, I can only see that if p and p+2 are a prime pair, then for m = p(p+2) we have the extra solution to x^2 = 1 (mod p(p+2)) of x = p+1 (mod p(p+2)).

   So, for each element in the list 2,3,…,m-2, its inverse is also in the list. Note that the list has an even number of elements, so we may pair off the elements into mutual inverses and so each pair contributes a factor of 1, so
   2*3*….*(m-2) = 1 (mod m). That leaves 1*(m-1) = -1 (mod m), combining =>
   (m-1)! = -1 (mod m) QED

Post a reply