XLII: Ask anything. Hope this helps.
Notation/definitions:
- Integer x is a
divisor of integer y if and only if there is an integer q such that x*q=y.
- A
prime number is an integer greater than 1 whose only positive divisors are 1 and itself.
- Integers x and y are
coprime if and only if there is no prime number that is a divisor of both x and y (i.e., gcd(x,y)=1).
- phi is
Euler's totient function.
- n is some integer such that n>=2.
- Z_n is the
ring of integers modulo n.
- y is an
inverse of x in Z_n if and only if (x*y)
mod(n)=1.
Lemma: If nonzero element x of Z_n is invertible (i.e., it has an inverse) then the inverse is unique.
proof: If xy=xz=1 (under ring multiplication), then (y)(xy)=(y)(xz)=(y)(1), (yx)y=(yx)z=y, and y=z=y. QED.
Theorem: Nonzero element x of Z_n is invertible if and only if x and n are coprime.
proof:
1) Assume that x and n are coprime. Then, by
Euler's totient theorem, (x*y)mod(n)=1 where y=x^(phi(n)-1), so (y)mod(n) is the unique inverse of x.
2) Assume that x and n are not coprime. Then, there is a prime number p that is a prime factor of both x and n, so that x=p*w and n=p*m for some positive integers w and m. Assume (to the contrary) that y is an inverse of x. Then, there is an integer z such that x*y=z*n+1. Therefore, p*w*y=z*p*m+1, p*(w*y-z*m)=1, and p is a divisor of 1, which is a contradiction.
QED.
Corollary: The number of invertible elements of Z_n equals phi(n).
proof: Zero is never invertible and nonzero x are invertible if and only if x and n are coprime. QED.
Special cases:
a) 1 and n-1 are invertible as themselves in Z_n.
b) If the inverse of x is y, then the inverse of y is x.
c) If n=p where p is prime, then Z_p is a
field, which means that every nonzero element of Z_p is invertible.
CC Code:
Code:
//////////////////////////////////////
//////////////////////////////////////
/*
Language = c++ -ansi -std=c++98 -fno-nonansi-builtins -Werror -Wold-style-cast -pedantic -Wall -W -Wfloat-equal -Wpointer-arith -Wcast-qual -Wcast-align -Wwrite-strings -Wconversion -Wsign-compare
Author = John - CorporalCaptain @ TrekBBS
Date = February 20, 2014
Specification = "OK." means no bugs detected.
Configure min_n and max_n for limits.
Configure do_display switches for miscellaneous info.
Configure do_check switches to perform checks or disable for speed.
*/
//////////////////////////////////////
// switches:
unsigned int min_n = 2; // >= 2
unsigned int max_n = 20; // <= square root of UINT_MAX+1
bool do_display_totient = true;
bool do_check_inverses = true;
bool do_check_non_inverses = true;
//////////////////////////////////////
#include <iostream>
//////////////////////////////////////
unsigned int gcd (unsigned int a, unsigned int b) { // See http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
while (b != 0) {
unsigned int t = b;
b = a % b;
a = t;
}
return a;
}
unsigned int totient (unsigned int x) { // See http://en.wikipedia.org/wiki/Euler's_totient_function
unsigned int t = 0;
for (unsigned int j=1; j<=x; j++)
if (gcd(j,x) == 1)
t++;
return t;
}
unsigned int my_exp (unsigned int x, unsigned int y, unsigned int n /* >=2 */) { // (x^y) mod n, by successive squaring
unsigned int x_to_2_to_j = x; // j=0
unsigned int a = 1;
while (y != 0) {
if ((y & 1) == 1) a = (a * x_to_2_to_j /* overflow possible here for large n */) % n;
x_to_2_to_j = (x_to_2_to_j * x_to_2_to_j /* overflow possible here for large n */) % n;
y = y >> 1; // j++
}
return a;
}
//////////////////////////////////////
int main (int argc, char * argv []) {
(void) argc;
(void) argv;
try {
for (unsigned int n=min_n; n<=max_n; n++) {
std::cout << std::endl;
std::cout << "n = " << n << std::endl;
const unsigned int totient_n = totient (n);
if (do_display_totient)
std::cout << "totient = " << totient_n << std::endl;
unsigned int num_invs = 0;
for (unsigned int x=0; x<n; x++) {
////////
std::cout << "x = " << x << " 1/x = ";
bool has_inverse = (gcd(x,n) == 1);
if (has_inverse) {
num_invs++;
unsigned int inv_x = my_exp (x, totient_n-1, n);
std::cout << inv_x;
if (do_check_inverses) {
if (1 != ((x*inv_x)%n))
throw "Bug detected in calculation of inverse";
}
} else {
std::cout << "-";
if (do_check_non_inverses) {
for (unsigned int y=0; y<n; y++)
if (1 == ((x*y)%n))
throw "Bug detected in determination of inverse non-existence";
}
}
////////
std::cout << std::endl;
}
if (totient_n != num_invs)
throw "Bug detected in calculation of number of inverses";
}
std::cout << std::endl;
std::cout << "OK." << std::endl;
}
catch (const char * message) {
std::cerr << "Exception: " << message << "." << std::endl;
}
catch (...) {
std::cerr << "Unknown exception." << std::endl;
}
return 0;
}
//////////////////////////////////////
//////////////////////////////////////
Output:
Code:
n = 2
totient = 1
x = 0 1/x = -
x = 1 1/x = 1
n = 3
totient = 2
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = 2
n = 4
totient = 2
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = -
x = 3 1/x = 3
n = 5
totient = 4
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = 3
x = 3 1/x = 2
x = 4 1/x = 4
n = 6
totient = 2
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = -
x = 3 1/x = -
x = 4 1/x = -
x = 5 1/x = 5
n = 7
totient = 6
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = 4
x = 3 1/x = 5
x = 4 1/x = 2
x = 5 1/x = 3
x = 6 1/x = 6
n = 8
totient = 4
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = -
x = 3 1/x = 3
x = 4 1/x = -
x = 5 1/x = 5
x = 6 1/x = -
x = 7 1/x = 7
n = 9
totient = 6
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = 5
x = 3 1/x = -
x = 4 1/x = 7
x = 5 1/x = 2
x = 6 1/x = -
x = 7 1/x = 4
x = 8 1/x = 8
n = 10
totient = 4
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = -
x = 3 1/x = 7
x = 4 1/x = -
x = 5 1/x = -
x = 6 1/x = -
x = 7 1/x = 3
x = 8 1/x = -
x = 9 1/x = 9
n = 11
totient = 10
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = 6
x = 3 1/x = 4
x = 4 1/x = 3
x = 5 1/x = 9
x = 6 1/x = 2
x = 7 1/x = 8
x = 8 1/x = 7
x = 9 1/x = 5
x = 10 1/x = 10
n = 12
totient = 4
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = -
x = 3 1/x = -
x = 4 1/x = -
x = 5 1/x = 5
x = 6 1/x = -
x = 7 1/x = 7
x = 8 1/x = -
x = 9 1/x = -
x = 10 1/x = -
x = 11 1/x = 11
n = 13
totient = 12
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = 7
x = 3 1/x = 9
x = 4 1/x = 10
x = 5 1/x = 8
x = 6 1/x = 11
x = 7 1/x = 2
x = 8 1/x = 5
x = 9 1/x = 3
x = 10 1/x = 4
x = 11 1/x = 6
x = 12 1/x = 12
n = 14
totient = 6
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = -
x = 3 1/x = 5
x = 4 1/x = -
x = 5 1/x = 3
x = 6 1/x = -
x = 7 1/x = -
x = 8 1/x = -
x = 9 1/x = 11
x = 10 1/x = -
x = 11 1/x = 9
x = 12 1/x = -
x = 13 1/x = 13
n = 15
totient = 8
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = 8
x = 3 1/x = -
x = 4 1/x = 4
x = 5 1/x = -
x = 6 1/x = -
x = 7 1/x = 13
x = 8 1/x = 2
x = 9 1/x = -
x = 10 1/x = -
x = 11 1/x = 11
x = 12 1/x = -
x = 13 1/x = 7
x = 14 1/x = 14
n = 16
totient = 8
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = -
x = 3 1/x = 11
x = 4 1/x = -
x = 5 1/x = 13
x = 6 1/x = -
x = 7 1/x = 7
x = 8 1/x = -
x = 9 1/x = 9
x = 10 1/x = -
x = 11 1/x = 3
x = 12 1/x = -
x = 13 1/x = 5
x = 14 1/x = -
x = 15 1/x = 15
n = 17
totient = 16
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = 9
x = 3 1/x = 6
x = 4 1/x = 13
x = 5 1/x = 7
x = 6 1/x = 3
x = 7 1/x = 5
x = 8 1/x = 15
x = 9 1/x = 2
x = 10 1/x = 12
x = 11 1/x = 14
x = 12 1/x = 10
x = 13 1/x = 4
x = 14 1/x = 11
x = 15 1/x = 8
x = 16 1/x = 16
n = 18
totient = 6
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = -
x = 3 1/x = -
x = 4 1/x = -
x = 5 1/x = 11
x = 6 1/x = -
x = 7 1/x = 13
x = 8 1/x = -
x = 9 1/x = -
x = 10 1/x = -
x = 11 1/x = 5
x = 12 1/x = -
x = 13 1/x = 7
x = 14 1/x = -
x = 15 1/x = -
x = 16 1/x = -
x = 17 1/x = 17
n = 19
totient = 18
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = 10
x = 3 1/x = 13
x = 4 1/x = 5
x = 5 1/x = 4
x = 6 1/x = 16
x = 7 1/x = 11
x = 8 1/x = 12
x = 9 1/x = 17
x = 10 1/x = 2
x = 11 1/x = 7
x = 12 1/x = 8
x = 13 1/x = 3
x = 14 1/x = 15
x = 15 1/x = 14
x = 16 1/x = 6
x = 17 1/x = 9
x = 18 1/x = 18
n = 20
totient = 8
x = 0 1/x = -
x = 1 1/x = 1
x = 2 1/x = -
x = 3 1/x = 7
x = 4 1/x = -
x = 5 1/x = -
x = 6 1/x = -
x = 7 1/x = 3
x = 8 1/x = -
x = 9 1/x = 9
x = 10 1/x = -
x = 11 1/x = 11
x = 12 1/x = -
x = 13 1/x = 17
x = 14 1/x = -
x = 15 1/x = -
x = 16 1/x = -
x = 17 1/x = 13
x = 18 1/x = -
x = 19 1/x = 19
OK.
Tested for:
Code:
unsigned int min_n = 2;
unsigned int max_n = 2000;
bool do_display_totient = true;
bool do_check_inverses = true;
bool do_check_non_inverses = true;
That reminds me of Deep Thought.
