Computing $R_{35}(1761^{4784})$

77 Views Asked by At

The exercise demands to compute: $R_{35}(1761^{4784})$

The relation $R_m(a)$ on $\mathbb{Z}$ is defined as follows: $a \equiv_m b$ $\Leftrightarrow$ a − b = km for some k $\Leftrightarrow$ $a \equiv_m R_m(a) $

I already know that the solution also solves $R_{5}(1761^{4784})=1$ since $R_{5}(R_{5}(1761)^{4784})=R_{5}((1)^{4784})=1$. The next step would be to find $R_{7}(1761^{4784})=?$

Once we we know $R_{5}(1761^{4784})=1$ and $R_{7}(1761^{4784})=?$ we can use the Chinese Remainder Theorem to find the solution.

2

There are 2 best solutions below

2
On BEST ANSWER

Since $1761$ and $35$ are relatively prime, you can use Euler's theorem: we know $\varphi(35)=\varphi(5)\,\varphi(7)=24\;$ and $1761\equiv11\mod 35$, so $$1761^{4784}\equiv 11^{4784}\equiv11^{4784\bmod 24}=11^{8}\mod 35.$$ Next do successive squarings mod.35 : $$11^2\equiv 16\Rightarrow 11^4\equiv 16^2\equiv 11\Rightarrow 11^8\equiv 11^2\equiv \color{red}{16}\mod 35.$$

A solution with smaller moduli:

We have to compute $1761^{4784}$ modulo $5$ and modulo $7$ first, then use the inverse isomorphism of the Chinese remainder theorem to have the value mod. $35$.

As observed by the O.P., it is equal to $1$ mod. $45$. Modulo $7$, we have $1761\equiv 4$. Now $4$ has order $3$ mod.$7 $ ($4^2=16\equiv 2$, $4^3=64\equiv 1$). So $$1761^{4784}\equiv 4^{4784\bmod 3}=4^2\equiv 2 \mod 7.$$ To end the computation, we need a Bézout's relation between $5$ and $7$, e.g. $\;3\cdot 7-4\cdot 5=1$. Then $$1761^{4784}\equiv\begin{cases}\color{red}{1}\mod \color{red}{5}\\\color{blue}{2}\mod \color{blue}{7}\end{cases}\iff 1761^{4784}\equiv \color{red}{1}\cdot 3\cdot \color{blue}{7}-\color{blue}{2}\cdot4\cdot\color{red}{5}=-19\equiv 16\mod 35.$$

0
On

Note that $1761 = 3\cdot 587 \equiv 3\cdot(-1) \pmod{7}.$ Also $3^3 \equiv -1 \pmod{7}.$ Then

$$1761^{4784} \equiv 3^{4784}(-1)^{\mbox{even}} \equiv (3^{3})^{1584}3^2 \equiv (-1)^{\mbox{even}}9\equiv 2 \pmod{7}.$$

So we have your number is $1 \pmod{5}$ and $2 \pmod{7}$. By CRT, it's $16 \pmod{35}.$