Proving a function is bijective in a given modulus.

Question

I've been wondering how you can prove that the function $x^{2017}$ when we work in modulo $100019$ (which happens to be prime), has an inverse function? Sorry I don't have any experience in typing maths, so I'll try to describe the problem. So the function is, we substitute a positive integer ranging from $1$ to $100019$ into $x^{2017}$, then find the residue of the output number in modulo $100019$. So the domain is $1$ to $100019$. Furthermore, how can we find $f^{-1}(99999)$ where the $f^{-1}$ is the inverse of this function described?

So far my attempts included to try and notice any patterns emerging in the residues when I substituted in numbers from $1$ to $12$, using a computer program. My main problem is proving that this function is one to one. Can someone please give me directions?

Edit: I have edited my original post, to specify p as 2017.

Answer 1

This follows directly from Fermat's little theorem, which also gives you the inverse itself.

There's a lot of material online on this matter, and there are many books on Abstract Algebra that prove this theorem, usually in the study of Group theory

Answer 2

I'll answer the general question:

For what prime numbers $p,q$ is the function

$$f(x)=x^p \pmod q$$

invertible.

The question started out with asking to prove invertibility for any $p$ and $q=100019$. Then, after I answered that it was wrong for $p=2$ and "for (generally) many p", the OP specified $p=2017$ and remarked that he/she generalized from this specific case because of tests with small values.

It turns out the OP is almost right: The above defined function $f$ is invertible for primes $p,q$ if and only if prime $p$ does not divide $q-1$.

If $q$ is a prime, then let's first remark that $f(0) = 0 \pmod q$ and $f(x) \neq 0$ for $x \neq 0 \pmod q$, since $q$ is a prime: A number not divisible by $q$, raised to any positive power, is still not divisible by $q$. So we can forget about the $0$ from now on: $f(0)=0$ and $f^{-1}(0)=0$ and we assume that any chosen number is not $=0 \pmod q$.

Since our function $f$ is mapping the finite set of $q$ equivalence classes$\pmod q$ to the finite set of $q$ equivalence classes$\pmod q$, shwowing that $f$ is bijective is the same as showing it is injective. We therefore have to see under what conditions

$$ x_1^p = x_2^p \pmod q$$

can be true. This can be rewritten as

$$ \left(\frac{x_1}{x_2}\right)^p = 1 \pmod q$$

If there exists some $r \neq 1$ with $r^p=1 \pmod q$, then our function is not injective, as we have $f(1)=f(r)=1 \pmod q$. On the other hand, if there does not exist such r, then (as we have seen above) from $ x_1^p = x_2^p \pmod q$ follows $\frac{x_1}{x_2}=1 \pmod q$, which means $x_1=x_2 \pmod q$ and thus our function is injective. It remains to find out if such $r$ exist.

The non-zero equivalence classes$\pmod q$ form a finite group (https://en.wikipedia.org/wiki/Group_(mathematics)) with respect to multiplication. One important property for finite groups $G$ is that for every element $a \in G$ it holds $a^{\left|G\right|}=e$, where $|G|$ is the number of elements in $G$ and $e$ is the neutral element of the operation. Since we are talking about multiplication$\pmod q$, this neutral element is the equivalence class containing 1. The number of elements in our group is $q-1$ (all equivalence classes except the 0 which has no inverse), so we get:

For any number $x \neq 0 \pmod q$ it holds that $x^{q-1}=1 \pmod q$.

This is also known as Fermat's Little Theorem: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

In group theory, the order of an element $x$ (order($x$)) is defined as the smallest positive n (if it exists) such that $x^n=e$. It turns out that the order of an element is a divisor of all integers for which $x^n=e$ holds. See again https://en.wikipedia.org/wiki/Group_(mathematics) for details.

Now we can attack our problem: Is there a number $r \neq 1 \pmod q$ such that $r^p=1 \pmod q$? We know that also $r^{q-1}=1 \pmod q$ (Fermat's Little Theorem). So what is the order of $r$? We have

$$\rm{order}(r) | p $$ and $$\rm{order}(r) | q-1,$$ hence $$\rm{order}(r) | gcd(p,q-1)$$.

Now since $p$ is a prime, the gcd is either $p$ or 1. If $p$ does not divide $q-1$, then the gcd is 1 and hence we have $\rm{order}(r)=1$, which means $r^1=1 \pmod q$ and therefore $r=1 \pmod q$. In other words, the only $r$ with $r^p=1 \pmod q$ is $r=1 \pmod q$ and thus $f$ is injective, hence bijective and hence invertible.

If $p$ does divide $q-1$, then the gcd is $p$ and we have

$$\rm{order}(r) | p$$

which is inconclusive: $\rm{order}(r)$ could be 1 or $p$.

A deeper look into the structure of the multiplicative group $\pmod q$ shows that it is cyclic, that means there exists an element $g$ such that order$(g)=q-1$ (see https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n under Structure/Powers of odd primes). That means that for $r=g^\frac{q-1}{p} \pmod q$ we have $r^p=g^{q-1}=1 \pmod q$ and since order$(g)=q-1$, $r \neq 1 \pmod q$. In this case our function $f$ is not injective, not bijective and not invertible.

To apply that to the original problem with $q=100019$, we need to find the prime divisors of $q-1=100018$ which is facorized as $2*43*1163$. So $f(x)=x^p \pmod {100019}$ is invertible for any $p\neq 2,43, 1163$.