1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Arithmetic Congruence

  1. Oct 15, 2014 #1
    1. The problem statement, all variables and given/known data

    Determine whether there is a positive integer k so that the congruence is satisfied.

    2k ≡ 1 (mod 11)


    2. Relevant equations

    gcd(2k,11) = 1


    3. The attempt at a solution

    Well, I know the answer is false. Because of Fermat's Little Theorem, 2k ≡ 2 (mod 11)

    But I'm not satisfied with this answer. How could I show the answer to #1?
     
  2. jcsd
  3. Oct 15, 2014 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    No, Fermat's Little Theorem tells you 2^11=2 (mod 11). That doesn't tell you it's false because you only need to find one value of k such that 2^k=1 (mod 11). What can you do with 2^11=2 (mod 11)?
     
  4. Oct 15, 2014 #3

    RUber

    User Avatar
    Homework Helper

    Modular multiplication is periodic.
     
  5. Oct 16, 2014 #4
    Oh good point... I'm not sure, I'm trying to work this out
     
  6. Oct 16, 2014 #5

    RUber

    User Avatar
    Homework Helper

    If 2 =2 mod 11, that means 2=11k+2.
    2 times that is 11(2k)+4 =4 mod k.
    By fermat's little theorem above, if you repeat that process 10 times, you will get back to 2^11=2 mod 11, and the cycle repeats.
    Either 1 mod 11 is in the first 10 powers of 2, or it won't be found in any of them.
     
  7. Oct 16, 2014 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You are trying to solve 2^k=1 (mod 11) and you have 2^11=2 (mod 11). Look at those two things and try not to think very hard.
     
  8. Oct 16, 2014 #7
    So do what RUber said? I feel like there is a faster way than checking 10 powers of 2... I know the answer is false from doing that. However, you are hinting at something simpler but I really don't know what. I just started learning modules.
     
  9. Oct 16, 2014 #8

    RUber

    User Avatar
    Homework Helper

    You don't need to check the powers of two.
    Notice that when you multiply (a mod 11) by two, your result (mod 11) will be 2a.
    So you get:
    2, 4, 8, 16 = 5 mod 11, 10, 20 = 9 mod 11, ...
    If you get back to 2 without seeing 1, there is no power of 2 that will give you 1 mod 11.
    However, you may be wondering how you got back to 2 if that is the case.
     
  10. Oct 16, 2014 #9
    Where are the 10 and 20 coming from?
     
  11. Oct 16, 2014 #10

    RUber

    User Avatar
    Homework Helper

    Multiplying by 2. That's how this works.
    16 = 5 mod 11, so 2*16 = 2*5 mod 11= 10 mod 11.
    2(10 mod 11)= 2*10 mod 11 = 20 mod 11 = 9 mod 11.
     
  12. Oct 16, 2014 #11
    Wait doesn't fermat's little theorem say 210 = 1 mod 11 ? That's all I need right
     
  13. Oct 16, 2014 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I am hinting think about dividing 2^11=2 (mod 11) by 2. What does that give you? In general, you can't divide by an arbitrary number modulo something so just think of it as a guess. What is your guess for what 2^10 mod (11) might be? If you can confirm that guess is true, then you are done.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Modular Arithmetic Congruence
  1. Modular arithmetic (Replies: 3)

  2. Modular arithmetic (Replies: 3)

  3. Modular arithmetic (Replies: 6)

  4. Modular Arithmetic (Replies: 23)

  5. Modular arithmetic (Replies: 3)

Loading...