1
$\begingroup$

Question at the end: Prove that the number of elements of $(\mathbb Z / n\mathbb Z)^\times$ is $\varphi(n)$ where $\varphi$ denotes the Euler function. I’ve demonstrated that it works for all n up to 12... Work showing n=1-12

It seems kinda obvious that not only does $\varphi(n)$ give the number of elements of $(\mathbb Z / n\mathbb Z)^\times$, but also the list of numbers are the same.

Question: I need a nudge in the right direction here. I can see that it works but I’m not sure how the remainders being equal to the relatively prime factors connects in a proof.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ In my reality, this is the definition of $\phi.$ Do you have a different definition? $\endgroup$ – B. Goddard May 31 '18 at 22:26
  • $\begingroup$ The definition I have for $\varphi(n)$ is the number of elements in a such that a<n and (a,n)=1. $\endgroup$ – Kaleb Allinson May 31 '18 at 22:46
  • $\begingroup$ So the problem comes down to showing that the invertible elements are exactly those which are relatively prime. $\endgroup$ – B. Goddard May 31 '18 at 23:32
  • $\begingroup$ What do you mean by invertible elements? $\endgroup$ – Kaleb Allinson Jun 1 '18 at 4:02
  • $\begingroup$ The ring $(Z/nZ)^\times$ is the set of invertible elements or "units". $\endgroup$ – B. Goddard Jun 1 '18 at 11:38
1
$\begingroup$

The key to these kinds of things is a clever observation called Bezout's Lemma. It says that if $x$ and $y$ are natural numbers with highest common factor equal to $d$, then you can find integers $a$ and $b$ such that $$ ax + by = d. $$ It is proved by applying Euclid's algorithm repeatedly and keeping track of what is happening. The relevance here is that if $m$ is relatively prime to $n$, then you have $$ am + bn = 1 $$ for some numbers $a$ and $b$. i.e. given such $m$, you can find $a$ with $$ am = (\text{multiple of}\ n) + 1... $$

$\endgroup$
  • $\begingroup$ OK, so does this reasoning work? Since $\bar{a}\bar{c}=\bar{1}$ Is the requirement for $(\mathbb{Z}/n\mathbb{Z})^x$... then $\bar{ac}=\bar{1}$ so $ac + kn = ny +1$ ... it follows that $ac + (k-y)n =1$. So we know that a and n are relatively prime and that for every a there is one c with the correct (k-y) chosen to go with the c needed to make $\bar{a} \bar{c}=\bar{1}$. So each a that makes $\bar{a} \bar{c}=\bar{1}$ true matches with one of the a’s from (a,n)=1 $\endgroup$ – Kaleb Allinson Jun 1 '18 at 3:51
  • $\begingroup$ Yeah. OK so I think we were kind of working on opposite ends of the problem. So one strategy to solve this is to take the two sets A = {invertible elements mod n} and B = {numbers less than n and coprime to n} and show A = B. So to do that we often do two separate aguments: 1. $ A \subset B$ and 2. $B \subset A$. So above I outlined the proof of "If m is coprime to n, then m is invertible mod n". You are essentially discussing "If a is invertible mod n, then a and n are relatively coprime". For your step you need slightly more than the literal statement of Bezout I gave above. $\endgroup$ – T_M Jun 1 '18 at 4:39
  • $\begingroup$ You need to know that the hcf of x and y really is the smallest number you can make via ax + by where a and b are integers $\endgroup$ – T_M Jun 1 '18 at 4:40
1
$\begingroup$

The criterion for $ax \equiv b \pmod{n}$ is that $(a,n) \mid b$.

If $a$ is invertible then $ax \equiv 1 \pmod{n}$ has a solution. So $(a,n) \mid 1$. So $(a,n) =1$. And vice versa.

$\endgroup$
  • $\begingroup$ OK, that makes sense! Thanks! $\endgroup$ – Kaleb Allinson Jun 1 '18 at 4:17
0
$\begingroup$

Hint

An element $\bar{a}$ (where $a=0, \dotsc, n-1$) is invertible in $\mathbb{Z/n}$ iff $a$ is relatively prime to $n$.

$\endgroup$
  • 2
    $\begingroup$ that seems basically to be the content of the problem $\endgroup$ – Andres Mejia May 31 '18 at 22:20
  • $\begingroup$ What do you mean by invertible? $\endgroup$ – Kaleb Allinson Jun 1 '18 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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