# Modular Arithmetic Congruence

1. Oct 15, 2014

### jreis

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. Oct 15, 2014

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

3. Oct 15, 2014

### RUber

Modular multiplication is periodic.

4. Oct 16, 2014

### jreis

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

5. Oct 16, 2014

### 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.

6. Oct 16, 2014

### Dick

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.

7. Oct 16, 2014

### jreis

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.

8. Oct 16, 2014

### 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.

9. Oct 16, 2014

### jreis

Where are the 10 and 20 coming from?

10. Oct 16, 2014

### 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.

11. Oct 16, 2014

### jreis

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

12. Oct 16, 2014

### Dick

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.