1. ## Modular arithmetic.

Why does $2^{10}\equiv1mod(11)$ and $2^{30}\equiv1mod(31)$ imply that

$2^{341}-2$ is divisible by both 11 and 31?

Thanks for any help

Is it because:

$2^{341}={2^{10}}^{30}*2^{41}\equiv2^{41}={(2^{10}) }^4*2\equiv2mod(341)$

2. Originally Posted by hmmmm
Why does $2^{10}\equiv1mod(11)$ and $2^{30}\equiv1mod(31)$ imply that

$2^{341}-2$ is divisible by both 11 and 31?

Thanks for any help

Is it because:

$2^{341}={2^{10}}^{30}*2^{41}\equiv2^{41}={(2^{10}) }^4*2\equiv2mod(314)$
$\displaystyle 2^{300} \equiv 258~\text{(mod 314)}$

and
$\displaystyle 2^{41} \equiv 202~\text{(mod 314)}$

-Dan

3. sorry I keep doing this it should be 341 not 314 really sorry I have edited the thread

4. Originally Posted by hmmmm
sorry I keep doing this it should be 341 not 314 really sorry I have edited the thread
(chuckles) I should have caught that myself, I kept trying to put in 341 in my calculator...

-Dan

5. Originally Posted by hmmmm
Why does $2^{10}\equiv1mod(11)$ and $2^{30}\equiv1mod(31)$ imply that

$2^{341}-2$ is divisible by both 11 and 31?

Thanks for any help

Is it because:

$2^{341}={2^{10}}^{30}*2^{41}\equiv2^{41}={(2^{10}) }^4*2\equiv2mod(341)$
The first case is simple: $341 \equiv 1~\text{(mod 10)} \implies 2^{341} \equiv 2^{1}~\text{(mod 11)}$

That's directly by the (slightly more general case of) Fermat's little theorem.

I'm still working on the next part, but I note that $341 \equiv 11~\text{(mod 30)} \implies 2^{341} \equiv 2^{11}~\text{(mod 31)}$. since you are given that $2^{10} \equiv 1~\text{(mod 11)}$ and $2^{30} \equiv 1~\text{(mod 31)}$ this has the feel of some kind of division algorithm in the works.

-Dan