RankRizz
JEE MAIN 2021 · 27 AUG S2+4MEDIUMTRANSCRIBED

JEE Main 2021 Mathematics question — Divisibility and remainder problems

3×722+2×1022−443 \times 7^{22} + 2 \times 10^{22} - 44 when divided by 18 leaves the remainder _________.

SOLUTION

We are asked to find the remainder obtained when the quantity 3×722+2×1022−443 \times 7^{22} + 2 \times 10^{22} - 44 is divided by 1818. In modular-arithmetic language, this means that we must evaluate the given expression modulo 1818, i.e. find its value in (mod18)\pmod{18}.

First, we note that for any integers aa and bb, the basic property of congruences is

a≡b(modm)    ⟹    a⋅c≡b⋅c(modm),a \equiv b \pmod{m} \;\;\Longrightarrow\;\; a \cdot c \equiv b \cdot c \pmod{m},

and

a≡b(modm),  c≡d(modm)    ⟹    a±c≡b±d(modm).a \equiv b \pmod{m},\; c \equiv d \pmod{m} \;\;\Longrightarrow\;\; a \pm c \equiv b \pm d \pmod{m}.

We shall therefore replace each large power by its much smaller remainder modulo 1818 and then combine the results.

Step 1: Evaluate 722(mod18).7^{22} \pmod{18}.

We first look for a pattern in the powers of 77 modulo 1818:

71=7≡7(mod18).7^1 = 7 \equiv 7 \pmod{18}.

72=49≡49−2 ⁣× ⁣18=49−36=13(mod18).7^2 = 49 \equiv 49 - 2\!\times\!18 = 49 - 36 = 13 \pmod{18}.

Now multiply again by 77:

73  =  72×7=13×7=91≡91−5 ⁣× ⁣18=91−90=1(mod18).7^3 \;=\; 7^2 \times 7 = 13 \times 7 = 91 \equiv 91 - 5\!\times\!18 = 91 - 90 = 1 \pmod{18}.

We have reached 73≡1(mod18).7^3 \equiv 1 \pmod{18}. This is extremely useful because now every third power will repeat the remainder 11. In other words,

73k≡1(mod18)for every integer k.7^{3k} \equiv 1 \pmod{18}\quad\text{for every integer }k.

We write 2222 as a multiple of 33 plus the remainder:

22=21+1=3×7+1.22 = 21 + 1 = 3 \times 7 + 1.

So

722=721+1=721 71=(73)7 7.7^{22} = 7^{21 + 1} = 7^{21}\,7^1 = (7^3)^7 \, 7.

Because 73≡17^3 \equiv 1, we replace it by 11:

(73)7 7≡17 7=7(mod18).(7^3)^7 \, 7 \equiv 1^7 \, 7 = 7 \pmod{18}.

Thus we have

722≡7(mod18).7^{22} \equiv 7 \pmod{18}.

Step 2: Evaluate 1022(mod18).10^{22} \pmod{18}.

We again look for a pattern, this time in the powers of 1010 modulo 1818:

101=10≡10(mod18).10^1 = 10 \equiv 10 \pmod{18}.

Now square that value:

102=100≡100−5 ⁣× ⁣18=100−90=10(mod18).10^2 = 100 \equiv 100 - 5\!\times\!18 = 100 - 90 = 10 \pmod{18}.

Notice that the remainder has come back to 1010. Therefore a second multiplication by 1010 will do the same:

103=102×10≡10×10=100≡10(mod18).10^3 = 10^2 \times 10 \equiv 10 \times 10 = 100 \equiv 10 \pmod{18}.

Hence once we reach the power 22, every additional power leaves the remainder unchanged at 1010. Concretely, for all positive integers n≥1,n \ge 1,

10n≡10(mod18).10^n \equiv 10 \pmod{18}.

In particular,

1022≡10(mod18).10^{22} \equiv 10 \pmod{18}.

Step 3: Substitute the reduced remainders into the original expression.

We have obtained

722≡7(mod18),7^{22} \equiv 7 \pmod{18},

and

1022≡10(mod18).10^{22} \equiv 10 \pmod{18}.

Thus

3×722+2×1022−443 \times 7^{22} + 2 \times 10^{22} - 44

becomes

3×7+2×10−44(mod18).3 \times 7 + 2 \times 10 - 44 \pmod{18}.

Carrying out the multiplications gives

21+20−44(mod18).21 + 20 - 44 \pmod{18}.

Add the first two numbers:

21+20=41,21 + 20 = 41,

so we now have

41−44=−3(mod18).41 - 44 = -3 \pmod{18}.

Step 4: Convert the negative remainder to a positive one.

A remainder of −3-3 can be made positive by adding 1818 (because adding or subtracting any multiple of the modulus does not change a congruence):

−3+18=15.-3 + 18 = 15.

Therefore

−3≡15(mod18).-3 \equiv 15 \pmod{18}.

The required non-negative remainder is thus 1515.

So, the answer is 1515.

Tagged Divisibility and remainder problems. Machine-assigned, so read it as a strong shortlist rather than a verdict.

TopicDivisibility and remainder problems
TypeNumerical answer