If, for natural numbers 𝑎,𝑏,𝑛
\[a \times b \equiv 1 \pmod n\]
is it obvious that either
\[a \equiv b \equiv 1 \pmod n\]
or
\[a \equiv b \equiv -1 \pmod n\]
Does this require special justification?
(is it one of those maths results that looks obvious but isn't)
consider 2 × 3 (mod 5)
one of many examples found with Haskell:
[ (a, b, n) | n <- [1..], a <- [1..n-1], b <- [a+1 .. n-1], (a * b) `mod` n == 1, not (mod a n == 1 && mod b n == 1 || mod a n == n - 1 && mod b n == n - 1) ]
nope, consider 3^2 (mod 8)
if x^2 = 1 (mod n) then x is called "self-inverse"
```
ghci> take 5 [ (a, n) | n <- [1..], a <- [1..n-1], (a * a) `mod` n == 1, not (mod a n == 1|| mod a n == n - 1) ]
[(3,8),(5,8),(5,12),(7,12),(4,15)]
```
@rzeta0 - Or try multiplying 5 and 3 mod 7.
There's a lot known about this issue:
https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n
Tariq
claude
John Carlos Baez