Using Modular Arithmetic to Solve Congruence Equations

[jreis]

Homework Statement

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

2^k ≡ 1 (mod 11)

Homework Equations

gcd(2^k,11) = 1

The Attempt at a Solution

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

But I'm not satisfied with this answer. How could I show the answer to #1?

 

[Dick]

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)?

 

[RUber]

Modular multiplication is periodic.

 

[jreis]

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)?

Oh good point... I'm not sure, I'm trying to work this out

 

[RUber]

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.

 

[Dick]

Oh good point... I'm not sure, I'm trying to work this out

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.

 

[jreis]

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.

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.

 

[RUber]

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.

 

[jreis]

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.

Where are the 10 and 20 coming from?

 

[RUber]

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.

 

[jreis]

Wait doesn't fermat's little theorem say 2¹⁰ = 1 mod 11 ? That's all I need right

 

[Dick]

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.

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.