Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Invertible elements in Zn

  1. Jul 23, 2011 #1
    Can we describe describe n such that Z_n has exactly 12 invertible elements?

    Thank you
     
  2. jcsd
  3. Jul 23, 2011 #2

    jambaugh

    User Avatar
    Science Advisor
    Gold Member

    By invertible elements I presume you mean multiplicative inverses.

    Start with the fact that if n is prime then [itex]Z_n[/itex] 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 [itex]Z_n[/itex] are not invertible?
    Consider if [itex]a[/itex] is a zero-divisor inf [itex]Z_n[/itex] i.e. if there is a [itex]b\ne 0[/itex](mod n) such that [itex]ab \equiv 0[/itex] (mod n).

    Then [itex]a[/itex] 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 [itex] a [/itex] has no inverse in [itex]Z_n[/itex] then it must be a zero divisor.

    So the number of invertible elements in [itex]Z_n[/itex] 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.
     
  4. Jul 23, 2011 #3
    Thank you for the response,

    If I have not made a mistake, I believe I have shown that 13 is the only possibility.
     
  5. Jul 23, 2011 #4
    If I recall, the inverse phi function is difficult. There doesn't seem to be any general formula.
     
  6. Jul 23, 2011 #5
    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.
     
  7. Jul 23, 2011 #6

    I like Serena

    User Avatar
    Homework Helper

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

    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....
     
    Last edited by a moderator: May 5, 2017
  8. Jul 23, 2011 #7
    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
     
  9. Jul 23, 2011 #8

    I like Serena

    User Avatar
    Homework Helper

    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).
     
  10. Jul 23, 2011 #9
    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.
     
  11. Jul 23, 2011 #10
    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.
     
    Last edited: Jul 24, 2011
  12. Jul 24, 2011 #11
    Thank you Steve, no problem.
     
  13. Jul 24, 2011 #12

    I like Serena

    User Avatar
    Homework Helper

    The type of question (and the questions in your previous threads) seem to imply you're learning new fields of mathematics.
     
  14. Jul 24, 2011 #13

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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:

    [tex]\phi(n)\geq \sqrt{n}~\text{for}~n\geq 6[/tex]

    So if we see when [itex]\sqrt{n}\geq 12[/itex], 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 [itex]\phi(n)=12[/itex].
     
  15. Aug 13, 2011 #14
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook