1. ## modular arithmetic help

Hey everyone, I am finding these difficult and need some help solving these by hand.

1. $x \equiv 10^{100} \ mod \ 1001$, so I want the remainder of $\frac{10^{100}}{1001}$.

2. solve $26^{24} \equiv 1 \ (mod \ 35)$, so I am trying to use Euler's Theorem with a=26 and n=35.

Any help would be very nice.

Thanks.

2. Originally Posted by Nguyen
Hey everyone, I am finding these difficult and need some help solving these by hand.

1. $x \equiv 10^{100} \ mod \ 1001$, so I want the remainder of $\frac{10^{100}}{1001}$.

2. solve $26^{24} \equiv 1 \ (mod \ 35)$, so I am trying to use Euler's Theorem with a=26 and n=35..
Outline strategy for 1.: $1001 = 7\times 11\times 13$, so use Fermat's little theorem to find $10^{100}$ mod 7, mod 11 and mod 13. Then use the Chinese remainder theorem to piece the results together.

For 2., you can't "solve" something that isn't an equation. But if you want to verify that $26^{24} \equiv 1 \pmod {35}$ then use a similar strategy to 1., namely factorise 35 (and check that the result holds mod 5 and mod 7).