Question 20

Let $$𝑓$$ be the function defined by $$𝑓(𝑛)$$ = remainder when $$n^{n}$$ is divided by $$7$$, for all positive integers $$𝑛$$. Find the smallest positive integer $$𝑇$$ such that $$f(n+T)=f(n)$$ for all positive integers $$n$$.


Correct Answer: 42

The mapping to be studied is
$$f(n)=n^{\,n}\pmod{7}, \qquad n\in\mathbb{N}.$$
We want the smallest positive integer $$T$$ such that

$$f(n+T)=f(n)\quad\text{for every positive integer }n.$$

The residue of $$n^{\,n}$$ (mod $$7$$) depends on

  • the base $$n$$ modulo $$7$$, and
  • the exponent $$n$$ modulo the Euler totient $$\phi(7)=6$$ (by Fermat’s Little Theorem, because any number that is not a multiple of $$7$$ satisfies $$a^{6}\equiv1\pmod 7$$).

Therefore the value of $$f(n)$$ is completely determined by the ordered pair

$$\bigl(n\bmod 6,\;n\bmod 7\bigr).$$

This pair repeats whenever $$n$$ is increased by a common multiple of $$6$$ and $$7$$, i.e. by $$\operatorname{lcm}(6,7)=42$$. Hence

$$f(n+42)=f(n)\quad\forall\,n\in\mathbb{N},$$

so $$T=42$$ is a period.

Next, we prove that no smaller $$T$$ can work.

Case 1: $$7\nmid T$$.

Choose $$n=7k$$ for some $$k\ge1$$. Then $$n\equiv0\pmod7$$ and $$f(n)=0$$. Since $$7\nmid T$$, we have $$n+T\not\equiv0\pmod7$$, so the base of $$(n+T)^{\,n+T}$$ is not divisible by $$7$$; its remainder cannot be $$0$$. Thus $$f(n+T)\ne f(n)$$, contradicting the requirement. Hence $$7$$ must divide every admissible $$T$$.

Case 2: $$6\nmid T$$ (but we already know $$7\mid T$$).

Take $$n$$ that satisfies the simultaneous congruences

$$n\equiv0\pmod6,\qquad n\equiv3\pmod7.$$

(Such an $$n$$ exists by the Chinese Remainder Theorem.) Here $$n\equiv3\pmod7$$, so the base is $$3$$, which is coprime to $$7$$. Because $$n\equiv0\pmod6$$, we have
$$f(n)=3^{\,n}\equiv3^{\,0}\equiv1\pmod7.$$ Since $$6\nmid T$$, we get $$n+T\not\equiv0\pmod6$$, so $$(n+T)\bmod6\ne0$$ while $$n+T\equiv3\pmod7$$ (because $$7\mid T$$). Thus
$$f(n+T)=3^{\,n+T}\equiv3^{\,r}\pmod7,$$ where $$r=(n+T)\bmod6\ne0$$. The possible powers $$3^{\,r}\pmod7$$ for $$r=1,2,3,4,5$$ are $$3,2,6,4,5$$β€”none equals $$1$$. Hence $$f(n+T)\ne f(n)$$, contradicting the requirement. Therefore $$6$$ must also divide every admissible $$T$$.

Combining the two cases, any valid period $$T$$ must be a multiple of both $$6$$ and $$7$$, i.e. a multiple of $$42$$. The smallest such positive integer is $$42$$ itself.

Hence the least positive period is
$$\boxed{42}.$$

Get AI Help

Video Solution

video

Book Free CAT Mentorship

Get personalized CAT strategy from a 99%iler

500+ students mentored
CAT mentor
banner

banner

50,000+ JEE Students Trusted Our Score Calculator

Predict your JEE Main percentile, rank & performance in seconds

Ask AI