Subscribe via feed.

## Integer Arithmetic

Posted by Chris on May 19, 2012 – 5:57 am

This page is for information only. It will experience “creeping beauty” over time.

You are welcome to post on it, but I will edit, delete, merge it as I see fit.
Contributor’s will be acknowledged.

I’m (generally) only going to deal with the positive integers. Including the negative integers (and 0) makes for a lot of pain for little gain. In particular, writing inequalities is far easier if we assume that all the integers are ≥ 0. The extension to all the integers should be self-evident.

Glossary:
ET = “Euler’s theorem”
FLT = “Fermat’s little theorem”
IFF = “if and only if”. This is much the same as “necessary and sufficient”,
“<=>” and “implies and is implied by”.
TFTOA = The Fundamental Theorem of Arithmetic
WLOG = “without loss of generality”
a|b => “a divides b”
a¦b => “a doesn’t divide b”

I use: “so”, “thus”, “hence”, “therefore”, “gives”, “implies” and “=>” interchangeably

This post is under “Tom” and has 7 respond so far.

### 7 Responds so far- Add one»

1. 1. Chris Said：

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：

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 = p1 p2 … pm = q1 q2 … qn.
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 23. 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 p1|N, so p1|q1 q2 … qn. But by the corollary to Euclid’s lemma, p1 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 p1. 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：

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: n1 + n2 = (mq1 + r1) + (mq2 + r2)
= m(q1 + q2) + (r1 + r2) = r1 + r2 (mod m)

Multiplication: n1 n2 = (mq1 + r1)(mq2 + r2)
= m(mq1q2 + q1r2 + q2r1) + r1 r2 = r1 r2 (mod m)

Exponentiation: If a = b (mod m), then an = bn (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
ap-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 => ap-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 = {r1, r2,…, rφ(m)} where the ri are the integers ≤ m that are coprime to m. Let aS = {ar1, ar2, …, arφ(m)}. Each element of aS must be distinct, mod m, because if ari = arj (mod m), then by cancellation ri = rj and that is only possible if
i = j (by definition of ri in S). Since each ari 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
ar1 * ar2 * … * arφ(m) = r1 * r2 * … * 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 = p1^n1 * p2^n2 * … then φ(m) = m(1 – 1/p1)(1 – 1/p2) …, where the pi 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 = p1p2p3, where the pi are distinct primes. Initially assume that all m integers are coprime to m. Then correct that by noting that there are m/p1 integers that are divisible by p1, m/p2 integers that are divisible by p2 and m/p3 integers that are divisible by p3. So far that means that φ(m) = p1p2p3 – (m/p1 + m/p2 + m/p3). But now we have overcounted the corrections: m/(p1p2) of those are divisible by both p1 and p2, m/(p2p3) are divisible by both p2 and p3 and m/(p3p1) that are divisible by both p3 and p1. But we have again overcounted the corrrections as m/(p1p2p3) (= m/m = 1 in this example) are dvisible by all three of p1, p2 and p3. Allowing for all the corrections => φ(m) =
m – (m/p1 + m/p2 + m/p3) + (m/(p1p2) + m/(p2p3) + m/(p3p1)) – m/(p1p2p3) and after some jiggling about we get φ(m) = m(1 – 1/p1)(1- 1/p2)(1- 1/p3) as can be verified by simply expanding the latter.

If there had been N distinct primes, we’d have got
φ(m) = m – Σm/pi+ Σm/(pipj) – Σm/(pipjpk) + … ± Σm/(pipjpk…pN)
= m ∏(1 – 1/pi), 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 pi’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 = p1^n1 p2 p3, 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 = pn, we get φ(pn) = pn(1 – 1/p) = pn-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：

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 = p1p2…pn + 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 pn is the nth prime, then by definition, ∏(pn) = n. Subsituting pn for x in the asymptotic equation => n ~ pn/ln(pn) and then pn ~ n ln(pn). Sadly that isn’t very useful.

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

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

The follow lists n, pn, and the error with the first and second estimators.
103, 7919, 12.8%, -11.6%
106, 15 485 863, 10.8%, -6.2%
109, 22 801 763 489, 9.1%, -4.2%
1012, 29 996 224 275 833, 7.9%, -3.2%

I did a check for pn ~ n ln(n) and pb ~ n (ln(n) + ln(ln(n)) -1) and got:
103, -12.8%, -0.99%
106, -10.8%, -0.29%
109, -9.1%, -0.21%
1012, -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：

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
anx = 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：

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

Intro. Consider solving, for x, the equation: x2 = a (mod p), where p
is prime and a is coprime to p. Raising both sides to the power (p-1)/2 =>
xp-1 = a(p-1)/2 (mod p)
Fermat’s little theorem => xp-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 ap-1 = 1 (mod p),
or if you prefer, (a/p)2 = 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:
x2 = 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

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

By the definitiion, (a/p)(b/p) = (ab/p), and it follows that (a2/p) = (a/p)2 = 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：

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 ab1 = ab2 (mod m) and by
the cancellation law we’d have b1 = b2 (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