Determining the Number of Invertible Elements in Zn

[arthurhenry]

Can we describe describe n such that Z_n has exactly 12 invertible elements?

Thank you

 

[jambaugh]

By invertible elements I presume you mean multiplicative inverses.

Start with the fact that if n is prime then $Z_n$ is a field i.e. all elements but zero have inverses.

So clearly there is one value n=13 where this is true.

The more general question is whether there are other values of n > 13 where only 12 of the elements have inverses. (for n< 13, you don't have enough elements).

So in general for n composite, which elements of $Z_n$ are not invertible?
Consider if $a$ is a zero-divisor inf $Z_n$ i.e. if there is a $b\ne 0$(mod n) such that $ab \equiv 0$ (mod n).

Then $a$ cannot have an inverse else multiplication by it in the last eqn above yields b = 0 violating the assumption.

I think you can then use Euler's theorem to show the reverse is true, if $a$ has no inverse in $Z_n$ then it must be a zero divisor.

So the number of invertible elements in $Z_n$ is the number of positive integers less than n and mutually prime to n. (LCD = 1).

From that, you can begin iterating cases, n=14, n=15, and so on to see what happens and see if you can make some broad statements.

 

[arthurhenry]

Thank you for the response,

If I have not made a mistake, I believe I have shown that 13 is the only possibility.

 

[SteveL27]

So the number of invertible elements in $Z_n$ is the number of positive integers less than n and mutually prime to n. (LCD = 1).

From that, you can begin iterating cases, n=14, n=15, and so on to see what happens and see if you can make some broad statements.

If I recall, the inverse phi function is difficult. There doesn't seem to be any general formula.

 

[arthurhenry]

I am not sure if I understand that comment...Are you saying that to be able to answer the question one needs a "inverse phi function"?

I just would like to be able solve the question.

 

[I like Serena]

phi is Euler's totient function:
http://en.wikipedia.org/wiki/Euler%27s_totient_function"

In particular:
"In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n (i.e. having no common positive factors other than 1)."

An element in Z_n is invertible (with respect to multiplication) iff it is coprime with n.

So the inverse phi function of 12 should give you an n such as you're looking for...

 

[arthurhenry]

Yes, I have been looking at some entries on the web for the inverse function, but none clearly spells out what it is. Some of these are rather involved articles.
question again: what is this formula that, as you say, I can plug 12 into and get the answer. Thank you

 

[I like Serena]

Your question looks like a homework question (is it?).
Forum policy (for a number of good reasons) is not to give straight answers in such cases, sorry.

The wikipedia article contains a table with values for phi.
Find one that says 12 (other than the one belonging to n=13).

 

[arthurhenry]

There are guidelines to this forum for people to read.One of the the well known guideline is that "people should not do Your homework for you" and also there exists a section where one asks homework questions.
If you are not going to believe one's integrity, I(i.e. If I am posting this question where I am not supposed to, chances are I will also lie in my response to your question and say "No, it is not a homework question")

If you look at the my last, say, 10 posts, it would be rather difficult to decide how many courses I would be simultaneously enrolled in for the breadth of questions I pose be such. So, instead of policing people (in effect insulting), perhaps you should choose not to respond at all.

To answer your question, no this is not a homework question and I am not sure how long it has been I was in a class.

Grumpy, yes, and perhaps I will feel apologetic in the morning, but not as of yet.

 

[SteveL27]

I am not sure if I understand that comment...Are you saying that to be able to answer the question one needs a "inverse phi function"?

I just would like to be able solve the question.

Sorry, I was making a more general remark. I didn't mean to introduce confusion.

If n is a positive integer, phi(x) is the number of positive integers less than n that are relatively prime to n. You are given 12, and asked to find all x such that phi(x) = 12. So in that sense, you do need the the value of the inverse phi function of 12.

So if you had the inverse phi function -- which has no convenient formula that I know of; or if it does, it's complicated -- you could solve your problem. But you don't need that ... you just need to solve the problem for 12, which is much easier.

If I just confused the issue, please ignore my post. My remark was much more general and not really of any help to your question. You only need to concentrate on finding all the x such that phi(x) = 12. That's a much easier problem than finding all the x such that phi(x) = n for arbitrary n.

 

[arthurhenry]

Thank you Steve, no problem.

 

[I like Serena]

The type of question (and the questions in your previous threads) seem to imply you're learning new fields of mathematics.

 

[micromass]

There are guidelines to this forum for people to read.One of the the well known guideline is that "people should not do Your homework for you" and also there exists a section where one asks homework questions.
If you are not going to believe one's integrity, I(i.e. If I am posting this question where I am not supposed to, chances are I will also lie in my response to your question and say "No, it is not a homework question")

If you look at the my last, say, 10 posts, it would be rather difficult to decide how many courses I would be simultaneously enrolled in for the breadth of questions I pose be such. So, instead of policing people (in effect insulting), perhaps you should choose not to respond at all.

To answer your question, no this is not a homework question and I am not sure how long it has been I was in a class.

Grumpy, yes, and perhaps I will feel apologetic in the morning, but not as of yet.

Homework can be taken to be very broad. If you read the rules, then you would see that even self-studing would fall under homework. So if you are self-studying and if you are working a problem from a book, this belongs in the homework forums. In any case, there is no need to start raging against ILS...Anyway, the Euler totient function has some nice bounds:

$$\phi(n)\geq \sqrt{n}~\text{for}~n\geq 6$$

So if we see when $\sqrt{n}\geq 12$, we get that n=144. This means that you only need to check until n=144 to see whether there is an element such that $\phi(n)=12$.

 

[arthurhenry]

I am reading this reply by you only now Micromass, thank you.
For some reason (mostly because it appears as a problem on a final exam), I assumed it would have some other, perhaps easier, solution. It seems like once 144 is determined, one calculates this by brute force.

Yes, most of my questions are self study questions, and I will try to post them from now on in the section you suggested; I really did not know the rules. I assumed, if I were assigned a problem, then it was fair game to ask it here. My apologies