Find the smallest $a\in\mathbb{N}$, so that $a\equiv3\cdot 5^4\cdot 11\cdot 13^3 \pmod 7$

Question

The problem I am trying to solve is:

Find the smallest $a\in\mathbb{N}$, so that $a\equiv3\cdot 5^4\cdot 11\cdot 13^3 \pmod 7$.

I noticed that $3,5,11$ and $13$ are primes, but I've no idea how that is supposed to help me.

The solution is $4$, but why?

Answer 1

Note $13^{3} \equiv (-1)^{3} \equiv -1 \pmod 7$

Also, note that $5^{4} \equiv 25^{2} \equiv 4^{2} \equiv 2 \pmod 7$.

Thus $3 \times 5^{4} \times 11 \times 13^{3} \equiv 3 \times 2 \times (-3) \times (-1) \equiv 18 \equiv 4 \pmod 7$.

Answer 2

I first saw this question and got intimidated by the size of the number and then I realised that $a$ will always lie in between $0$ and $6$. Every natural number is congruent to one and only one number from the set $(0,1,2,3...n-1)$ $\mod n$.

$$5 = (7p -2)$$ $$3 = (7p +3)$$ $$11 = (7q-3)$$ $$13 = (7q-1)$$

Notice the product of the terms $$(7a + b)(7c + d) = 7m + cd$$

The remainder depends only on $cd$ since everything else is a multiple of $7$.

$$(7p + 3)(7p - 2)^{4}(7p - 3)(7q-1)^{3}$$

Similarly, the remainder with $7$ here is

$$3.(-2)^{4}.(-3).(-1)^{3} = 3.(16).(-3)(-1)$$

$$48.3 = 7.6.3 + 6.3$$

$$a \equiv 6.3 (\mod 7)$$

$$\implies a \equiv 18 (\mod 7)$$

$$\implies a \equiv 4 (\mod 7)$$