Results 1 to 3 of 3

Math Help - Minor point of clarification regarding congruencies

  1. #1
    Newbie BBAmp's Avatar
    Joined
    May 2010
    From
    Cleveland,OH/Madison,WI/Queens,NY
    Posts
    17

    Minor point of clarification regarding congruencies

    Hi,

    In my book there are many proofs that looks like this in the primitive roots chapter:

    a^{t+k\phi(m)} \equiv a^{t}(a^{k})^{\phi(m)} \equiv a^{t} \equiv 1 (mod \ m)

    For the record for this particular proof t is the order of a (mod \ m), k is an integer, and \phi(m) is Euler's totient function.

    The last step (where you end up with a^{t} \equiv 1 (mod \ m) at the end) is the only part that isn't clear to me and would like someone to tell me if my justification is correct:

    The way I have justified the last step is that since (a, m) = 1 we can cancel a^{t} in a^{t}(a^{k})^{\phi(m)} \equiv a^{t} (since they are also congruent to each other... do congruencies work like this?) and get

    (a^{k})^{\phi(m)} \equiv 1 \equiv 1 (mod \ m).

    also since a^{t+k\phi(m)} \equiv (a^{k})^{\phi(m)} I can further cancel (a^{k})^{\phi(m)} to get:

    a^{t} \equiv 1(mod \ m).

    The problem is I still don't fully understand how congruencies work.

    If my justification is incorrect and if I had to write the proof on my own how would I get from

    a^{t+k\phi(m)} \equiv 1(mod \ m) to a^{t} \equiv 1 (mod \ m)?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by BBAmp View Post
    Hi,

    In my book there are many proofs that looks like this in the primitive roots chapter:

    a^{t+k\phi(m)} \equiv a^{t}(a^{k})^{\phi(m)} \equiv a^{t} \equiv 1 (mod \ m)

    For the record for this particular proof t is the order of a (mod \ m), k is an integer, and \phi(m) is Euler's totient function.

    The last step (where you end up with a^{t} \equiv 1 (mod \ m) at the end) is the only part that isn't clear to me and would like someone to tell me if my justification is correct:

    The way I have justified the last step is that since (a, m) = 1 we can cancel a^{t} in a^{t}(a^{k})^{\phi(m)} \equiv a^{t} (since they are also congruent to each other... do congruencies work like this?) and get

    (a^{k})^{\phi(m)} \equiv 1 \equiv 1 (mod \ m).

    also since a^{t+k\phi(m)} \equiv (a^{k})^{\phi(m)} I can further cancel (a^{k})^{\phi(m)} to get:

    a^{t} \equiv 1(mod \ m).

    The problem is I still don't fully understand how congruencies work.

    If my justification is incorrect and if I had to write the proof on my own how would I get from

    a^{t+k\phi(m)} \equiv 1(mod \ m) to a^{t} \equiv 1 (mod \ m)?
    If you don't fully understand congruences, you should go back and learn those before jumping into like order and primitive roots.

    Anyway,  (a^k)^{\phi(m)}\equiv1\bmod{m}\implies a^t(a^k)^{\phi(m)}\equiv a^t\cdot 1=a^t \bmod{m} .

    But you're given  \text{ord}_m(a)=t \implies a^t\equiv1\bmod{m} .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie BBAmp's Avatar
    Joined
    May 2010
    From
    Cleveland,OH/Madison,WI/Queens,NY
    Posts
    17
    I looked back and a small proof clarified everything. I believe this was the only thing that was confusing me in congruences so I am set for the coming chapters.

    Thanks for the help/advice!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Length of minor arc?
    Posted in the Trigonometry Forum
    Replies: 4
    Last Post: August 2nd 2011, 10:00 AM
  2. Minor help with integrals
    Posted in the Calculus Forum
    Replies: 2
    Last Post: June 3rd 2010, 11:01 AM
  3. Minor clarification on modulus graphs
    Posted in the Geometry Forum
    Replies: 4
    Last Post: January 19th 2010, 03:25 AM
  4. Two questions with angles and congruencies...
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: June 26th 2009, 05:51 PM

Search Tags


/mathhelpforum @mathhelpforum