Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Ok, so I know when $(a, m) = 1$, by Euler's Theorem, $a^{\phi(m)} \equiv 1 \mod m$. Since $\phi(323) = 288$, $a^{288} \equiv 1 \mod m$ when $(a, 323) = 1$. However, there are some elements $a$ such that $(a, 323) \not= 1$ and $a^{288} \not\equiv 1 \mod 323$. Since those elements do not have multiplicative inverses in $\mathbb{Z}/323$, how is it working that $x^n$ is invertible? Am I missing something?


Exercise I.8. Prove that $f : \mathbb{Z}/323 \to \mathbb{Z}/323$ given by $f(x) = x^n$ is a bijective map if $(n, 6) = 1$.

Proof. Assume that $(n, 6) = 1$. Then $2 \not\mid n$ and $3 \not\mid n$. Let $f(x) = x^n$. Now by Theorem 9.3, $\phi(323) = \phi(17 \cdot 19) = (17-1)(19-1) = 16 \cdot 18 = 288 = 2^5 \cdot 3^2$. We need $x$ such that $nx \equiv 1 \mod 288$. Since $2 \not\mid n$ and $ \not\mid n$, $(n, 288) = (n, 2^5 \cdot 3^2) = 1$. Then by Lemma 5.2, $nx \equiv 1 \mod 288$ has exactly one solution. That is, $n^{-1}$ exists in $\mathbb{Z}/288$. Then $f^{-1} = x^{n^{-1}}$ since $f^{-1}(f(x)) = f^{-1}(x^n) = (x^n)^{n^{-1}} = x^{n \cdot n^{-1}} \equiv x \mod 323$. Since $f$ is invertible, $f$ is bijective. $\blacksquare$

(Image version)

share|improve this question

2 Answers 2

It works here because $\,323 = 17\cdot 19\,$ is squarefree, so the following generalization of Euler-Fermat implies that if $\rm\,{\rm lcm}(16,18) = 144\mid e-1\,$ then $\, a^e\equiv a\pmod{323}\,$ for all $\,a.$ This fails if the modulus $\rm\,m = k d^2,\, d>1\,$ is not squarefree, since then $\rm\,(kd)^e \equiv 0^e \pmod{m}$ for all $\rm\,e\ge 2\,$ therefore the map $\rm\,f(x) = x^e\,$ is not $\,1$-$1,\,$ since $\rm\,f(kd)\equiv 0 \equiv f(0)\,$ but $\rm\,kd\not\equiv 0.$

Theorem $\ $ For natural numbers $\rm\:a,e,n\:$ with $\rm\:e,n>1$

$\qquad\rm n\:|\:a^e-a\:$ for all $\rm\:a\:\iff n\:$ is squarefree, and prime $\rm\:p\:|\:n\:\Rightarrow\: p\!-\!1\:|\:e\!-\!1$

Proof $\ (\Leftarrow)\ \ $ Since a squarefree natural divides another iff all its prime factors do, we need only show $\rm\:p\:|\:a^e\!-\!a\:$ for each prime $\rm\:p\:|\:n,\:$ or, that $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1} \equiv 1\pmod p,\:$ which, since $\rm\:p\!-\!1\:|\:e\!-\!1,\:$ follows from $\rm\:a \not\equiv 0\:$ $\Rightarrow$ $\rm\: a^{p-1} \equiv 1 \pmod p,\:$ by little Fermat.
$(\Rightarrow)\ \ $ See this answer

share|improve this answer

Note that $f$ being invertible doesn't mean that all elements of $\mathbb{Z} / 323\mathbb{Z}$ are invertible. That $f$ is an invertible map just means that there is an inverse map $g$ such that $$\begin{align} f \circ g &= 1 \\ g \circ f &= 1. \end{align} $$ That is: $f(g(x)) = x$ for all $x \in \mathbb{Z} / 323\mathbb{Z}$ and $g(f(x)) = x$ for all $\mathbb{Z} / 323\mathbb{Z}$. When we have such a $g$, we usually denote it by $f^{-1}$. So in your case $f(x) = x^{n^{-1}}$ where $n^{-1}$ is the inverse of $n$ in $\mathbb{Z} / 288\mathbb{Z}$

This relies in part on $n$ satisfying $(n, 6) = 1$.

share|improve this answer
    
No, it works because the modulus is squarefree. It fails otherwise - see my answer. –  Bill Dubuque Mar 10 at 16:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.