What is the remainder of

Question

$\dfrac{33^{100}}{50}$

I have done

$\dfrac{2×{33^{100}}}{100}$

But it is still complex. How can we calculate the remainder of a number divided by 100?

Answer 1

The fundamental idea you're overlooking is:

Let $m,n,d$ be positive integers. You have an equation

$$ m \equiv n \bmod d $$

if and only if the following two quantities are the same:

• The remainder when dividing by $m$ by $d$
• The remainder when dividing by $n$ by $d$

So, you can turn your "find a remainder" problem into a "do modular arithmetic" problem which leads to an easier "find a remainder" problem.

(incidentally, the theorem above works for all integers when stated appropriately — but it can be tricky to find the right statement because people don't all agree on what "remainder" means when negative numbers are involved)

Answer 2

$$33^2=(30+3)(30+3)\equiv9+2\cdot30\cdot3\equiv190-1$$

$$33^{4m}=(33^2)^{2m}\equiv(190-1)^{2m}\equiv(1-190)^{2m}\equiv1-\binom{2m}1190\pmod{100}$$

Here $4m=100$

Answer 3

Use Carmichael Function,,

as $(33,50)=1,$ and $\lambda(50)=20$

$$33^{20}\equiv1\pmod{50}$$

$$33^{20m}=(33^{20})^m\equiv1^m\pmod{50}$$

Here $20m=100\iff m=?$