# Number of invertible elements in a ring $\mathbb{Z}_n$.

I know that:

a number $$a\in\mathbb{Z}_n$$ is invertible iff $$\text{gcd}(a,n)=1$$.

So say $$n=2019$$. How can I find the number of invertible elements in $$\mathbb{Z_{2019}}$$? Surely testing $$2019$$ numbers for primality is out of the question.

Also, if $$a=32$$, what is its inverse? In my book they state that

An inverse in modular arithmetic is a number $$a\in\mathbb{Z}_n$$ if there exists a number in $$\mathbb{Z}_n$$ such that if multiplied by $$a$$ gives $$1$$.

So from this I understand that I need to find an $$x\in\mathbb{Z}$$ such that

$$32\cdot x\equiv 1(\text{mod}\ 2019).$$ This is the same as solving the diophantine equation

$$32x=1+2019y\Leftrightarrow32x-2019y=1,$$

which has trivial solution $$(x,y)=(-694,-11)$$. So the inverse of $$32$$ is $$-694?$$

• The number of invertible elements is given by the Euler totient function, which has an explicit formula in terms of the prime factorization. Look it up. – Teresa Lisbon Feb 5 '19 at 15:17
• Have you factored $2019$ yet? That would be a sensible first step in checking which numbers are coprime to it. – Servaes Feb 5 '19 at 15:18
• @астонвіллаолофмэллбэрг - We have not covered Eulers totient function and it's not part of this course. – Parseval Feb 5 '19 at 15:43
• @Servaes - Yes, just divided it by three since $2+0+1+9$ is divisible by $3$, so is $2019$. I got that $2019=3\cdot 673$. However, on an exam, I need to motivate how I know that $673$ is a prime, no calculators allowed. How Do I now find the coprimes? – Parseval Feb 5 '19 at 15:45
• Well it suffices to check that it is not divisible by the primes less than $\sqrt{673}<26$, which is a bit of work but not hard. Then a number is coprime to $2019$ if it is not divisible by $3$ and not divisible by $673$. I leave it to you to count how many such numbers there are. – Servaes Feb 5 '19 at 15:54

For the second question, your reasoning is correct. Indeed the inverse of $$32$$ in $$\Bbb{Z}/2019\Bbb{Z}$$ is $$-694$$, though perhaps a representative in the interval $$[0,2018]$$ is preferred.
For the first question, it helps to first know the prime factors of $$2019$$. It is not hard to check that $$2019=3\times673$$ and that $$3$$ and $$673$$ are prime. Then an integer in the interval $$[0,2018]$$ is coprime to $$2019$$ if and only if it is not divisible by $$3$$ and not divisible by $$673$$. I leave it to you (for now) to count how many such integers there are.
• Great! So to go from $-694$ to somewhere positive, I simply add $2019$ right? I'll give the first part a go and see what I can do. I'll return If I get stuck. – Parseval Feb 5 '19 at 16:01
• I don't understand why this is true: "Then an integer in the interval $[0,2018]$ is coprime to $2019$ if and only if it is not divisible by $3$ and not divisible by $673$." Could you please elaborate? – Parseval Feb 5 '19 at 16:13
• If an integer is not coprime to $2019$, then it shares a common prime factor with $2019$, which must be either $3$ or $673$ (or both). – Servaes Feb 5 '19 at 16:15