20251006 Senior Varsity Training

Problem 1

How many positive integers $n$ are there such that $n$ is a multiple of $5$, and the least common multiple of $5!$ and $n$ equals $5$ times the greatest common divisor of $10!$ and $n$?

Solution

Since

$$\begin{array}{rl}\mathrm{lcm}(5!,n)=5\gcd (10!,n)& ⟺\forall p\in \mathbb{P},{\nu }_p(\mathrm{lcm}(5!,n))={\nu }_p(5\gcd (10!,n))\\ & ⟺\forall p\in \mathbb{P},\max \{{\nu }_p(5!),{\nu }_p(n)\}=\min \{{\nu }_p(10!),{\nu }_p(n)\}+{\nu }_p(5)\end{array}$$

it follows that

$$\begin{array}{rl}|\{n:5\mid n\wedge \mathrm{lcm}(5!,n)=5\gcd (10!,n)\}|& =|\{n:\forall p\in \mathbb{P},(p=5\to {\nu }_p(n)\ge 1)\wedge \max \{{\nu }_p(5!),{\nu }_p(n)\}=\min \{{\nu }_p(10!),{\nu }_p(n)\}+{\nu }_p(5)\}|\\ & =\prod _{p\in \mathbb{P}}|\{{\nu }_p(n):(p=5\to {\nu }_p(n)\ge 1)\wedge \max \{{\nu }_p(5!),{\nu }_p(n)\}=\min \{{\nu }_p(10!),{\nu }_p(n)\}+{\nu }_p(5)\}|\\ & =|\{3,4,5,6,7,8\}||\{1,2,3,4\}||\{3\}||\{0,1\}|\\ & =48\end{array}$$

Problem 2

Call a positive integer $n$ extra-distinct if the remainders when $n$ is divided by $2$, $3$, $4$, $5$, and $6$ are distinct. Find the number of extra-distinct positive integers less than $1000$.

Solution

Since it is easy to prove that if there are two positive integers $x$ and $y$ such that $x\equiv y(\mathrm{mod}60)$, $x$ is extra-distinct iff $y$ is extra-distinct, and since it is easy to prove that all extra-distinct positive integers less than or equal to $60$ are $35$, $58$, and $59$, it follows that $n$ is extra-distinct iff

$$n\equiv 35(\mathrm{mod}60)\vee n\equiv 58(\mathrm{mod}60)\vee n\equiv 59(\mathrm{mod}60)$$

Therefore, the number of extra-distinct positive integers less than $1000$ is $49$.

Problem 3

Let $N$ be the greatest four-digit positive integer with the property that whenever one of its digits is changed to $1$, the resulting number is divisible by $7$. Let $Q$ and $R$ be the quotient and remainder, respectively, when $N$ is divided by $1000$. Find $Q+R$.

Solution

Let the digits of $N$ be $a$, $b$, $c$, and $d$, respectively, then $N$ satisfies the property iff

$$6+2b+3c+d\equiv 0(\mathrm{mod}7)\wedge 6a+2+3c+d\equiv 0(\mathrm{mod}7)\wedge 6a+2b+3+d\equiv 0(\mathrm{mod}7)\wedge 6a+2b+3c+1\equiv 0(\mathrm{mod}7)$$

Since

$$6+2b+3c+d\equiv 0(\mathrm{mod}7)\wedge 6a+2+3c+d\equiv 0(\mathrm{mod}7)\wedge 6a+2b+3+d\equiv 0(\mathrm{mod}7)\wedge 6a+2b+3c+1\equiv 0(\mathrm{mod}7)⟺a\equiv 5(\mathrm{mod}7)\wedge b\equiv 6(\mathrm{mod}7)\wedge c\equiv 2(\mathrm{mod}7)\wedge d\equiv 4(\mathrm{mod}7)$$

it follows that $N=5694$.

Therefore, $Q+R=699$.

Problem 4

Let $f$ be the unique function defined on positive integers such that

$$\sum _{d\mid n}f\left(\frac{n}{d}\right)d=1$$

for all positive integers $n$. What is $f(2023)$?

Solution 4

Solution

$$\forall n\in {\mathbb{Z}}_{+},\sum _{d\mid n}f\left(\frac{n}{d}\right)d=1⟺\forall n\in {\mathbb{Z}}_{+},\sum _{d\mid n}\frac{f(d)}{d}=\frac{1}{n}$$

Applying Möbius Inversion Formula yields

$$\begin{array}{rl}\forall n\in {\mathbb{Z}}_{+},\sum _{d\mid n}\frac{f(d)}{d}=\frac{1}{n}& ⟺\forall n\in {\mathbb{Z}}_{+},\frac{f(n)}{n}=\sum _{d\mid n}\mu (d)\frac{d}{n}\\ & ⟺\forall n\in {\mathbb{Z}}_{+},f(n)=\sum _{d\mid n}\mu (d)d\end{array}$$

Therefore,

$$\begin{array}{rl}f(2023)& =\sum _{d\mid 2023}\mu (d)d\\ & =96\end{array}$$

Problem 5

What is the smallest positive integer $n$ such that $20\equiv n^{15}(\mathrm{mod}29)$?

Solution

Applying Fermat’s Little Theorem yields

$$n^{28}\equiv 1(\mathrm{mod}29)$$ $$\begin{array}{rl}{n}^{28}\equiv 1(\mathrm{mod}29)& ⟺n^{14}\equiv 1(\mathrm{mod}29)\vee n^{14}\equiv 28(\mathrm{mod}29)\\ & ⟺n^{15}\equiv n(\mathrm{mod}29)\vee n^{15}\equiv 28n(\mathrm{mod}29)\end{array}$$

Therefore,

$$\begin{array}{rl}{n}^{15}\equiv 20(\mathrm{mod}29)& ⟹n\equiv 9(\mathrm{mod}29)\vee n\equiv 20(\mathrm{mod}29)\end{array}$$ $$9^{15}\equiv 9\cdot 3^{28}(\mathrm{mod}29)$$

Therefore, since applying Fermat’s Little Theorem yields

$$3^{28}\equiv 1(\mathrm{mod}29)$$

it follows that

$$9^{15}\equiv 9(\mathrm{mod}29)$$ $$20^{15}\equiv 20\cdot 7^{28}(\mathrm{mod}29)$$

Therefore, since applying Fermat’s Little Theorem yields

$$7^{28}\equiv 1(\mathrm{mod}29)$$

it follows that

$$20^{15}\equiv 20(\mathrm{mod}29)$$

Therefore,

$$n^{15}\equiv 20(\mathrm{mod}29)⟺n\equiv 20(\mathrm{mod}29)$$

Therefore, the smallest positive integer $n$ is $20$.

Problem 6

Find the last two digits of

$$17^{17^{17^{17}}}+18^{18^{18^{18}}}+19^{19^{19^{19}}}+20^{20^{20^{20}}}$$

Solution

It is easy to prove that the answer is equal to

$$\left(17^{17^{17^{17}}}+18^{18^{18^{18}}}+19^{19^{19^{19}}}+20^{20^{20^{20}}}\right)\mathrm{mod}100$$ $$\begin{array}{rl}17^{17^{17^{17}}}\mathrm{mod}4& =1^{17^{17^{17}}}\mathrm{mod}4\\ & =1\end{array}$$

Applying Euler’s Theorem yields

$$17^{17^{17^{17}}}\mathrm{mod}25=17^{17^{17^{17}}\mathrm{mod}20}\mathrm{mod}25$$

Applying Euler’s Theorem yields

$$\begin{array}{rl}17^{17^{17}}\mathrm{mod}20& =17^{17^{17}\mathrm{mod}8}\mathrm{mod}20\\ & =17^{1^{17}\mathrm{mod}8}\mathrm{mod}20\\ & =17\end{array}$$

Therefore,

$$\begin{array}{rl}17^{17^{17^{17}}}\mathrm{mod}25& =17^{17}\mathrm{mod}25\\ & =2\end{array}$$

Applying Chinese Remainder Theorem yields

$$17^{17^{17^{17}}}\mathrm{mod}4=1\wedge 17^{17^{17^{17}}}\mathrm{mod}25=2⟺17^{17^{17^{17}}}\mathrm{mod}100=77$$ $$\begin{array}{rl}18^{18^{18^{18}}}\mathrm{mod}4& =2^{18^{18^{18}}-2}\cdot 2^2\mathrm{mod}4\\ & =0\end{array}$$

Applying Euler’s Theorem yields

$$\begin{array}{rl}18^{18^{18^{18}}}\mathrm{mod}25& =18^{18^{18^{18}}\mathrm{mod}20}\mathrm{mod}25\\ & =18^{16}\mathrm{mod}25\\ & =1\end{array}$$

Applying Chinese Remainder Theorem yields

$$18^{18^{18^{18}}}\mathrm{mod}4=0\wedge 18^{18^{18^{18}}}\mathrm{mod}25=1⟺18^{18^{18^{18}}}\mathrm{mod}100=76$$ $$\begin{array}{rl}19^{19^{19^{19}}}\mathrm{mod}4& =(-1{)}^{19^{19^{19}}}\mathrm{mod}4\\ & =3\end{array}$$

Applying Euler’s Theorem yields

$$\begin{array}{rl}19^{19^{19^{19}}}\mathrm{mod}25& =19^{19^{19^{19}}\mathrm{mod}20}\mathrm{mod}25\\ & =19^{(-1{)}^{19^{19}}\mathrm{mod}20}\mathrm{mod}25\\ & =19^{19}\mathrm{mod}25\\ & =4\end{array}$$

Applying Chinese Remainder Theorem yields

$$19^{19^{19^{19}}}\mathrm{mod}4=3\wedge 19^{19^{19^{19}}}\mathrm{mod}25=4⟺19^{19^{19^{19}}}\mathrm{mod}100=79$$ $$\begin{array}{rl}20^{20^{20^{20}}}\mathrm{mod}100& =20^{20^{20^{20}}-2}\cdot 20^2\mathrm{mod}100\\ & =0\end{array}$$

Therefore,

$$\begin{array}{rl}\left(17^{17^{17^{17}}}+18^{18^{18^{18}}}+19^{19^{19^{19}}}+20^{20^{20^{20}}}\right)\mathrm{mod}100& =\left(17^{17^{17^{17}}}\mathrm{mod}100+18^{18^{18^{18}}}\mathrm{mod}100+19^{19^{19^{19}}}\mathrm{mod}100+20^{20^{20^{20}}}\mathrm{mod}100\right)\mathrm{mod}100\\ & =(77+76+79+0)\mathrm{mod}100\\ & =32\end{array}$$

Problem 7

Let $p$ be the least prime number that for which there exists a positive integer $n$ such that $n^4+1$ is divisible by $p^2$. Find the least possible $m$ such that $m^4+1$ is divisible by $p^2$.

Solution

Since

$$p^2\mid n^4+1⟹\gcd (n,p^2)=1$$

assume $n$ satisfies $\gcd (n,p^2)=1$.

Since

$$\begin{array}{rl}{p}^2\mid n^4+1& ⟹p^2\mid n^8-1\\ & ⟺n^8\equiv 1(\mathrm{mod}{p}^2)\end{array}$$

and since

$$\begin{array}{rl}{p}^2\mid n^4+1& ⟹p^2\nmid n^4-1\\ & ⟺n^4\not\equiv 1(\mathrm{mod}{p}^2)\end{array}$$

it follows that

$${\delta }_{p^2}(n)=8$$

Therefore,

$$\begin{array}{rl}{\delta }_{p^2}(n)\mid \phi (p^2)& ⟺8\mid p(p-1)\\ & ⟺8\mid p-1\end{array}$$

Therefore, since it is easy to prove that there exists a positive integer $n$ when $p=17$, it follows that $p=17$.

$$\begin{array}{rl}17^2\mid m^4+1& ⟹17\mid m^4+1\\ & ⟺m\equiv -2(\mathrm{mod}17)\vee m\equiv 2(\mathrm{mod}17)\vee m\equiv -8(\mathrm{mod}17)\vee m\equiv 8(\mathrm{mod}17)\end{array}$$

If $m=17k-2$,

$$\begin{array}{rl}17^2\mid m^4+1& ⟺(17k-2{)}^4+1\equiv 0(\mathrm{mod}17^2)\\ & ⟺-544k+17\equiv 0(\mathrm{mod}17^2)\\ & ⟺2k+1\equiv 0(\mathrm{mod}17)\\ & ⟺k\equiv 8(\mathrm{mod}17)\end{array}$$

If $m=17k+2$,

$$\begin{array}{rl}17^2\mid m^4+1& ⟺(17k+2{)}^4+1\equiv 0(\mathrm{mod}17^2)\\ & ⟺544k+17\equiv 0(\mathrm{mod}17^2)\\ & ⟺15k+1\equiv 0(\mathrm{mod}17)\\ & ⟺k\equiv 9(\mathrm{mod}17)\end{array}$$

If $m=17k-8$,

$$\begin{array}{rl}17^2\mid m^4+1& ⟺(17k-8{)}^4+1\equiv 0(\mathrm{mod}17^2)\\ & ⟺-34816k+4097\equiv 0(\mathrm{mod}17^2)\\ & ⟺9k+3\equiv 0(\mathrm{mod}17)\\ & ⟺k=11(\mathrm{mod}17)\end{array}$$

If $m=17k+8$,

$$\begin{array}{rl}17^2\mid m^4+1& ⟺(17k+8{)}^4+1\equiv 0(\mathrm{mod}17^2)\\ & ⟺34816k+4097\equiv 0(\mathrm{mod}17^2)\\ & ⟺8k+3\equiv 0(\mathrm{mod}17)\\ & ⟺k=6(\mathrm{mod}17)\end{array}$$

Therefore,

$$\begin{array}{rl}m& =\min \{134,155,179,110\}\\ & =110\end{array}$$

Problem 8

Let $a,b$ be positive integers. If for any positive integer $n$, we have $a^n+n\mid b^n+n$, prove $a=b$.

Solution

$$\forall n\in {\mathbb{Z}}_{+},a^n+n\mid b^n+n⟹\forall p\in \mathbb{P},a^{a(p-1)+p}+a(p-1)+p\mid b^{a(p-1)+p}+a(p-1)+p$$

Since applying Fermat’s Little Theorem yields

$$a^{a(p-1)+p}\equiv a(\mathrm{mod}p)$$

it follows that

$$a^{a(p-1)+p}+a(p-1)+p\equiv 0(\mathrm{mod}p)$$

Therefore,

$$\begin{array}{rl}{a}^{a(p-1)+p}+a(p-1)+p\mid b^{a(p-1)+p}+a(p-1)+p& ⟹a^{a(p-1)+p}+a(p-1)+p\equiv b^{a(p-1)+p}+a(p-1)+p(\mathrm{mod}p)\\ & ⟺a^{a(p-1)+p}\equiv b^{a(p-1)+p}(\mathrm{mod}p)\end{array}$$

Since applying Fermat’s Little Theorem yields

$$b^{a(p-1)+p}\equiv b(\mathrm{mod}p)$$

it follows that

$$a^{a(p-1)+p}\equiv b^{a(p-1)+p}(\mathrm{mod}p)⟺a\equiv b(\mathrm{mod}p)$$

Therefore,

$$\begin{array}{rl}\forall n\in {\mathbb{Z}}_{+},a^n+n\mid b^n+n& ⟹\forall p\in \mathbb{P},a\equiv b(\mathrm{mod}p)\\ & ⟺a=b\end{array}$$