4
$\begingroup$

My question is directly, how many elements are in the invertible set $Z_{35}$?

It's my understanding that for any $Z_n$, if $n$ is prime, then the number of invertible elements is equal to $n-1$. In addition, all elements that are invertible satisfy the formula $\gcd(x,n) = 1$. Thus, for $n = 35$, which is composed of two primes, the number of invertible elements should be $n-3$, or $32$. The non-invertible elements namely $0, 5, 7$.

Will someone please show me where I my logic is incorrect. This was a Coursera question that I missed four times, but I can't seem to figure out why unless I am misunderstanding something or missing something very obvious.

$\endgroup$
4
  • $\begingroup$ What about multiplies of $5$ and $7$? $\endgroup$
    – Marcin Łoś
    Commented Feb 23, 2014 at 23:15
  • 2
    $\begingroup$ The set isn't invertible. You're talking about the invertible elements. You may be interested in Euler's totient function $\varphi(n):=|(\Bbb Z/n\Bbb Z)^\times|$. It is multiplicative, which here means that $\varphi(35)=\varphi(5)\varphi(7)$ $=(5-1)(7-1)=24$. $\endgroup$
    – anon
    Commented Feb 23, 2014 at 23:18
  • $\begingroup$ Yeah, sorry, I just mis-worded that part of it. This is helpful also. Thank you. $\endgroup$
    – Hunter Rose
    Commented Feb 23, 2014 at 23:22
  • $\begingroup$ "In addition": that's not an addition; it's precisely the necessary and sufficient condition for $x$ to be invertible in $\Bbb Z_n$. As a corollary, if $n$ is prime, then every non zero element is invertible, so there are $n-1$ of them. $\endgroup$
    – user1007416
    Commented Jun 5, 2022 at 19:21

3 Answers 3

Reset to default
3
$\begingroup$

it is called as Euler-phi function.$\Phi (n)=|\{1\leq a <n|(a,n)=1\}|$.

And $\Phi(p)=p-1$ for prime numbers and it is multiplicative i.e if $(m,n)=1$ then $\Phi(mn)=\Phi(m)\Phi(n)$.When you know this,it is easy to compute. $$\Phi(35)=\Phi(7)\Phi(5)=6\cdot4=24$$

$\endgroup$
1
$\begingroup$

What is $\gcd(10,35)$? What is $\gcd(14,35)$? Can you begin to see from these examples which other non-invertible elements of $\mathbb{Z}_{35}$ you have been missing?

$\endgroup$
2
  • $\begingroup$ Gosh, I'm an idiot. Thank you for pointing out the very obvious thing I was missing. $\endgroup$
    – Hunter Rose
    Commented Feb 23, 2014 at 23:18
  • $\begingroup$ No worries, happens to all us sometimes :) $\endgroup$
    – Zev Chonoles
    Commented Feb 23, 2014 at 23:18
0
$\begingroup$

The formula for Euler's $\phi$ function answers that.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .