1

How can one calculate $342343^2$ mod $3$? I know that the answer is $1$.

And $342342^{1001}$ mod $5$.

I know that

$ 3^0 \mod 5 = 1 \\ 3^1 \mod 5 = 3 \\ 3^2 \mod 5 = 4 \\ 3^3 \mod 5 = 2 \\\\ 3^4 \mod 5 = 1 \\ 3^5 \mod 5 = 3 \\ 3^6 \mod 5 = 4 \\ $

So 1001 = 250 + 250 + 250 + 250 + 1, which is why the answer is also 1?

  • 2
    First order of business: Reduce the base. $34232\equiv 1 \pmod 3$ and $342342\equiv 2\pmod 5$. – Arthur Oct 31 '18 at 11:56
  • 1
    Do you know Fermat's little theorem $a^{p-1}\equiv 1 \mathrm{mod}\ p$ – OgvRubin Oct 31 '18 at 12:00
  • 1
    Steps for solution: (1) $342342 \equiv 2 \pmod5$ ...(2) $342342^{1001} \equiv 2^{1001}\pmod 5$ ...(3) $2^x\pmod 5$ is periodic in $x$, do the first few $x$ to discover what the pattern it. – GEdgar Oct 31 '18 at 12:00

3 Answers3

1

$$342342^{1001} \equiv2^{1001} \space \bmod5$$

$$2^{1001}=2 \times (2^4)^{250}\equiv2\times1^{250}\bmod 5=2$$

Case $342343^2 \bmod 3$ is even simpler. You can easily prove that $a^2\equiv 0 \bmod 3$ iff $a\equiv0\bmod3$. In all other cases $a^2\equiv 1 \bmod3$.

Number 342343 is not divisible by 3 so the result must be 1.

Saša
  • 15,906
0

First, Note that $$342342 = 34234*10+2= 34234*2*5 +2$$ So you have $$342342 \equiv 2 \pmod 5$$

Then, remember that $$\forall a,b,c,n \in \mathbb N, a \equiv b \pmod n \implies a^c \equiv b^c \pmod n$$

Therefore, $$342342^{1001} \equiv 2^{1001} \pmod 5$$

Finaly, note that $1001 = 1000+1 = 4*250 +1$ and try to conclude

F.Carette
  • 1,346
0

This is an observation but you can take it as an answer.

Let $n\in\mathbb{N}$ then $3|n\iff$ $3$ divides the sum of all the digits of $n$. Now consider $n=342343$ and sum of all of its digits $=19$. So clearly $n\equiv-2 (\mod 3)\implies n^2\equiv1(\mod 3)$ since $4\equiv 1(\mod 3)$.

For the second part observe this, $2^4\equiv 1(\mod 5)\implies 2^{250\times4}\equiv 1(\mod 5)\implies 2^{250\times 4+1}\equiv 2(\mod 5)\implies 2^{1001}\equiv 2(\mod 5)$

Now $342342\equiv 2(\mod 5)\implies 342342^{1001}\equiv 2^{1001}(\mod 5)\equiv 2(\mod 5)$

Sujit Bhattacharyya
  • 3,030