2
$\begingroup$

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?$

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Teresa Lisbon Feb 5 '19 at 15:17
  • 1
    $\begingroup$ Have you factored $2019$ yet? That would be a sensible first step in checking which numbers are coprime to it. $\endgroup$ – Servaes Feb 5 '19 at 15:18
  • $\begingroup$ @астонвіллаолофмэллбэрг - We have not covered Eulers totient function and it's not part of this course. $\endgroup$ – Parseval Feb 5 '19 at 15:43
  • $\begingroup$ @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? $\endgroup$ – Parseval Feb 5 '19 at 15:45
  • $\begingroup$ 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. $\endgroup$ – Servaes Feb 5 '19 at 15:54
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Parseval Feb 5 '19 at 16:01
  • $\begingroup$ That's right, and good luck. $\endgroup$ – Servaes Feb 5 '19 at 16:01
  • $\begingroup$ 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? $\endgroup$ – Parseval Feb 5 '19 at 16:13
  • $\begingroup$ 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). $\endgroup$ – Servaes Feb 5 '19 at 16:15
  • 1
    $\begingroup$ Thanks man, I eventually realised this after thinking harder than usual! $\endgroup$ – Parseval Feb 19 '19 at 21:08

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.