Results 1 to 6 of 6

Thread: Help With primitive roots

  1. #1
    Junior Member
    Joined
    Aug 2007
    Posts
    28

    Help With primitive roots

    Hi guys, i dont understand WHAT is going on in this question...

    How do they just "choose" 2, 3 and 5 to check for ?

    Also in the power why is it 1606/2 then 1606/11???

    I really dont understand whats going on

    heres the question and solution

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2006
    From
    San Diego
    Posts
    101
    Well remember by the Fermat-Euler theorem that $\displaystyle a^{\phi(n)} \equiv 1 \mod n$, where $\displaystyle \phi(n)$ is the number of things less than n that are relatively prime to n.

    Often times, a number doesn't need to be raised all to the way to $\displaystyle \phi(n)$ before it gives back 1 though.
    For example, $\displaystyle \phi(8) = 4$, and while $\displaystyle 3^4 = 81 \equiv 1 \mod 8$, it is also true that $\displaystyle 3^2 \equiv 1 \mod 8$. So 3 is not a primitive root mod 8.

    We call the order of a number the smallest positive number that number is raised to in order to get 1. In the above example, the order of 3 is 2, because $\displaystyle 3^2 \equiv 1\mod 8$, but no lower power will work.

    So a primitive root mod n is a number whose order is equal to $\displaystyle \phi(n)$. It is a proven fact that the order of a number will always divide $\displaystyle \phi(n)$. This fact will be used.

    In the problem you have, we are looking for primitive roots mod 1607.
    Now 1607 is prime, so $\displaystyle \phi(1607) = 1606$ because everything less than it is obviously relatively prime to it.

    If a number were NOT primitive, then its order would be less than 1606, but also its order would divide 1606.

    A good strategy for finding primitive roots is just to test numbers.
    1 is obviously not primitive because its order is 1.
    Looking at 2, we raise it to powers that divide 1606; Try raising it to 1303 power (which is 1606/2, as was done in the solution). Sure enough, this gives 1, so the order of 2 is at most 1303, which means 2 cannot be primitive. (by the way, I'm guessing you know how at least to raise numbers to very high powers using mods without working out massive calculations. On a normal day, outside the world of mods, $\displaystyle 2^{1303}$ is a daunting task at best.)
    Next we look at 3, and do the same thing. Again, we get 1 back, so 3 cannot be a primitive root.
    Now next would be 4, but 4 is skipped because it's a power of 2, and we already threw 2 away as a possibility.

    Next is 5, and actually the solution you posted has a typo in it.
    First we check the 1606/2 power, and instead of 1 we get -1. So far so good.
    Next we check 1606/11 power, and again we don't get 1. Good news again.
    Finally, we check the last power, which is 1606/73 (in the pic posted, they have this printed wrong) and again we don't get 1. So 1606 must be the order of 5, and so 5 is a primitive root.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2007
    Posts
    28
    Hey,thanks for the help..

    I still dont understand how you can just "divide" the number by 2 and know that it gives 1?

    I know (Now) its just easy to read the soultion and say "yes this gives 1" but when your trying to solve it from scratch, When i power numbers i use the fast powering algorithm, which is (relativley) time consuming, so how can i be trying all these numbers inorder to get somthing congruent to 1?

    for example there id need to calculate 2^803, which would take a good 5 minutes?

    Is the fast powering algorithm optimal to be using in an exam?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2006
    From
    San Diego
    Posts
    101
    Quote Originally Posted by BruceBronson View Post
    Hey,thanks for the help..

    I still dont understand how you can just "divide" the number by 2 and know that it gives 1?

    When i power numbers i use the fast powering algorithm, which is (relativley) time consuming, so how can i be trying out all these numbers inorder to get somthing congruent to 1?

    for example there id need to calculate 2^803, which would take a good 5 minutes?

    Is the fast powering algorithm optimal to be using in an exam?
    I've never heard it called that, but I'm sure that's the standard method. If it only takes 5 minutes to do that, you're probably using the right method.
    Of course I don't know your professor, but in my experience exam questions are not made unnecessarily complicated in terms of calculation.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2007
    Posts
    28
    Fast powering is the method where u have thre 3 columns and the first is half the entry in the previous, 2nd is the square mod m of the previous, and the last is the product of 2 entries mod m

    Is that the fastest possible way to do it?

    Ps. thanks for the help
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    The primitive root of a prime $\displaystyle p$ is such a number $\displaystyle a$ (say between $\displaystyle 1$ and $\displaystyle p-1$) so that the order of $\displaystyle a$ is $\displaystyle p-1$. Now by Fermat's theorem we know that $\displaystyle a^{p-1} \equiv 1$, but it is not necessaryiliy the smallest possible exponent. So we need to check whether or not it is the smallest.

    However, it does not need we need to show $\displaystyle a^k\not = 1$ for $\displaystyle k=1,2,...,p-2$ by checking each possible case. We can use the fact that the order of the element divides $\displaystyle p-1$ and just check the possible orders of an element. That is what the problem was doing.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jul 10th 2011, 05:15 PM
  2. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Nov 17th 2008, 08:09 PM
  3. Primitive roots
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Mar 15th 2007, 09:19 AM
  4. Primitive roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 21st 2006, 07:05 AM
  5. Primitive Roots
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 18th 2006, 01:43 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum