Question

Determine the integer x satisfying 1 <= x <= 55 and x is congruent to 2^13 mod 55

Answer 1

\[2^{13} = 2\times(2^{6})^2\]

Not sure what to do next

Answer 2

\[2^{13} \equiv x \mod 55 \Rightarrow 2^{13} - x \equiv 0 \mod 55\Rightarrow 2^{13} - x \equiv 0 \mod 5\]\[\Rightarrow 2^{13} - x \equiv 0 \mod 11\]

Answer 3

So I don't quite understand how the mod 55 changed to mod 5 and then 11

Answer 4

\[2^{13} - x \equiv 0 \mod 5\Rightarrow 2\cdot4^{3} - x \equiv 0 \mod 5\Rightarrow 3 - x \equiv 0 \mod 5\]
\[\Rightarrow 2 \cdot (2^{4})^{3} - x \equiv 0 \mod 11\]

if it's evenly divisble by 55 then it's evenly divisible by 5 and 11

Answer 5

ok, that makes sense but how do I solve for x?

Answer 6

\[2\cdot \left( 2^{3} \right)^{4}-x \equiv 0 \mod 11 \Rightarrow 2\cdot8^4-x \equiv 0 \mod 11\\]
\[\Rightarrow 2\cdot64^2-x \equiv 0 \mod 11\]\[64 \equiv 9 \mod 11\Rightarrow 81 \equiv 4 \mod 11 \Rightarrow x \equiv 8 \mod 11\]
but i goofed on the first so let's revisit that...

\[2^{13} - x \equiv 0 \mod 5 \Rightarrow 2\left( 2^4 \right)^3-x \equiv 0 \mod 5 \Rightarrow x \equiv 2 \mod 5\]

2^4 = 16 which is equivalent to 1 mod 5

so x must be equivalent to 8 mod 11 and 2 mod 5
so we have 8, 19, 30, 41 & 52

but 8 = 3 mod 5
19 = 4 mod 5
30 = 0 mod 5
41 = 1 mod 5
52 = 2 mod 5

so x = 52

Answer 7

How do you type the congruent sign in open study?

Answer 8

Alright, thanks for the help. :)

I think I found a little quicker way to do it though. I'll use equal signs instead of congruent cause I don't know how to type them.

\[x = 2^{13} = 2(2^6)^2 = 2(9)^2 = 2\times26 = 52 \mod 55\]

Answer 9

yeah, i'm not to well versed in all of this but that's the right answer. good job!

Answer 10

Well I just got 2 into a small enough power so that I could subtract 55 from it so:

\[2^{13} = 2(2^6-55)^2 = 2(9)^2 = 2(81-55) = 2(26) = 52 \mod 55\]

But yeah, it makes sense now, and that is what I need so thanks :D

Answer 11

@bbkzr31 that is that method by squaring
good job.