Results 1 to 2 of 2

Thread: Order of Integer Questions

  1. #1
    Member
    Joined
    Nov 2008
    Posts
    152

    Order of Integer Questions

    1) Show that if n is a positive integer and a and b are integers relatively prime to n such that $\displaystyle (ord_{n}a, ord_{n}b)$ = 1, then $\displaystyle ord_{n}(ab)$ = $\displaystyle ord_{n}a * ord_{n}b$

    2) Let p be a prime divisor of the Fermat number $\displaystyle F_{n} = 2^{2n} + 1$
    a) Show that $\displaystyle ord_{p}2 = 2^n + 1$
    b) From part (a), conclude that $\displaystyle 2^{n+1} \mid (p-1)$, so that p must be of the form $\displaystyle 2^{n+1}k + 1$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    For the first one...

    (By the way Fermat's number is from the form: $\displaystyle 2^{2^n}+1$ when $\displaystyle n=0,1,...$

    For your question now...

    I don't use to work with $\displaystyle ord$ notation, so...

    $\displaystyle ord_n(a)=t$, $\displaystyle ord_n(b)=s$ and $\displaystyle ord_{n}(ab)
    =w$

    From $\displaystyle ord_{n}(ab)$ which can be written as:

    $\displaystyle (ab)^w\equiv1(mod {n})$, we can deduce:

    $\displaystyle (ab)^{wt}\equiv 1(mod {n})$, and from $\displaystyle (a)^{wt}\equiv 1(mod {n})$, we get:

    $\displaystyle (b)^{wt}\equiv 1(mod {n})$

    From your first theorem on this subject of orders... we can say that: $\displaystyle {s}\mid {wt}$, but $\displaystyle gcd(w,t)=1$, hence: $\displaystyle {t}\mid {w}$...

    Similarly we can prove: $\displaystyle {s}\mid{w}$.

    Now, we have: $\displaystyle {t}\mid {w}$ and $\displaystyle {s}\mid {w}$, hence: $\displaystyle {ts}\mid {w}$.


    And the last part:

    We have given that:

    $\displaystyle a^t\equiv1(mod{n})$ and $\displaystyle b^s\equiv1(mod{n})$,
    so: $\displaystyle (ab)^{ts}=(a^t)^s(b^s)^t\equiv1(mod{n})$ and from the theorem I mentioned before we get: $\displaystyle {w}\mid {ts}$, and with the $\displaystyle {ts}\mid {w}$ (from the last part), we may deduce that $\displaystyle w=ts$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: Mar 6th 2011, 10:08 AM
  2. Order of Integer Question
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Oct 27th 2010, 08:51 PM
  3. Order of Integer Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 16th 2007, 05:45 PM
  4. Number theory, order of an integer
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 21st 2006, 05:53 AM
  5. order of an integer
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Nov 21st 2006, 05:37 AM

Search Tags


/mathhelpforum @mathhelpforum