recategorized by
3,214 views

12 Answers

Best answer
15 votes
15 votes

Remainder theorem can be used to find the remainder

Firstly we have to calculate the Euler Totient function of 9 i.e., $\phi (9)$ 

Euler totient function of of n gives the number of positive integers upto n which are relatively prime to n

Euler number of 9=$3^{2}$ i.e., $\phi (9)$= $9*[1-\frac{1}{3}] = 6$ which are 1,2,4,5,7,8

Given $\frac{4444^{4444}}{9}$

Using remainder theorem

$\frac{rem(4444/9)^{rem(4444/6)}}{9}$= $\frac{(7)^{4}}{9}$ = 7(remainder)

Hence option d) is the correct answer

edited by
15 votes
15 votes

(4444)4444 = (4437 + 7)4444 splitting so because 4437 is divisible by 9. (4+4+3+7=18).

By binomial theorem,

(4437 + 7)4444

= 4444C0 * (4437)0 * 74444 + 4444C1 * (4437)1 * 74443 ........... .... 4444C4444 * (4437)4444 * 70.

Each term of the above expansion from the second term onwards is divisible by 9 as it contains '4437' or some power of it. (Hence any of these terms will not have any effect on the remainder on dividing by 9).

Now our problem reduces to finding the remainder on dividing 4444C0 * (4437)0 * 74444 = 74444 by 9.(As this is the only term not containing 4437).

Now observe this chain of remainders on dividing 7 and its powers by 9:

7% 9=7

7% 9=4

7% 9=1

7% 9=7

.

.

.

.

We got the cycle of remainders which repeats after an interval of 3 (7-4-1-7-4-1......)

Since 4444 % 3(cycle length) = 1 and 1st number is above cycle is 7. So, 74444 on dividing by 9 gives 7 as the remainder.

option D.

 

12 votes
12 votes
$\dfrac{4444^{1}}{9} \implies \text{remainder} = 7$

$\dfrac{4444^{2}}{9} \implies \text{remainder} = 4$

$\dfrac{4444^{3}}{9} \implies \text{remainder} = 1$

$\implies \dfrac{(4444^{3})^{1481}\times 4444^{1}}{9} = \dfrac{1\times 4444}{9} = \dfrac{4444}{9} \implies \text{remainder} = 7$

So, the correct answer is $7.$
5 votes
5 votes

Euler's Theorem states that if two positive integers $n$ and $a$ are co-primes then
$$a^{\varphi(n)} \equiv 1 \pmod n$$

Where $\varphi(n)$ is Euler Totient function.

Let $a=4444, n=9$ and $\varphi(9) = \varphi(3^2) = 3^2-3^1=6$ [ref] we get
$$(4444)^6 \bmod 9 = 1  \ \ \ \  \ \ \ \ \ \cdots(1)$$
Remember, $444 = 2^2 \times 11 \times 101$ and $9 = 3^2$ are co-primes.

We will also need multiplication property of modular arithmetic

$$(A \times B) \bmod C = (A \bmod C \times B \bmod C) \bmod C$$
Note, this property can be directly extended to exponents as exponentials are nothing but repeated multiplication.

Now we have enough resources to find the answer.

$$\begin{align}(4444)^{4444} \bmod 9 &=(4444)^{(6 \times 740 + 4)} \bmod 9 \\ &= \left[(4444^6)^{740} \times (4444)^4\right] \bmod 9 \\ &= \left[ (4444^6)^{740} \bmod 9  \ \times \ (4444)^4 \bmod 9\right] \bmod 9 \\ &= \left[(4444^6 \bmod 9)^{740} \bmod 9 \times \ (4444)^4 \bmod 9\right] \bmod 9 \\\end{align}$$

Use $(1)$ in the above result to get,
$$\begin{align}(4444)^{4444} \bmod 9 &= (4444)^4 \bmod 9 \\ &=\left[ 4444 \bmod 9\right]^4 \bmod 9 \\ &= 7^4 \bmod 9 \\ &= \left[ 49 \bmod 9 \times 49 \bmod 9\right] \bmod 9 \\ &= 16 \bmod 9 \\ &= 7\end{align}\\$$


There is little advantage we get using Euler's Theorem. We can hit this problem without it, using just multiplication property of modular arithmetic.

Here something hard to identify initially, but true is $7^3 \equiv 1 \pmod 9$ $\therefore (7^3)^{1481} \equiv 1^{1481} \pmod 9 $ 

$$\begin{align}(4444)^{4444} \bmod 9 &= \left( 4444 \bmod 9 \right)^{4444} \bmod 9 \\ &= 7^{4444} \bmod 9 \\ &= \left[ 7^{4443} \times 7 \right] \bmod 9 \\ &= \left[ (7^3)^{1481} \times 7 \right] \bmod 9 \\ &= 7 \bmod 9 \\ &= 7\end{align}$$

HTH

edited by
Answer:

Related questions

4 votes
4 votes
1 answer
1
2 votes
2 votes
1 answer
3
2 votes
2 votes
1 answer
4
admin asked Mar 14, 2023
379 views
Let $m=2877426671$. It is known that $p=5754853343=2 m+1$ is a $10$ -digit prime number. What is $16^{m}(\bmod p)$ ?$1$$4$$16$$2877426671$$5754853342 \;($ which is actua...