Let $n \geq 2$ be an integer. Prove that if $$\frac{n^2+4^n+7^n}{n}$$is an integer, then it is divisible by 11.
Problem
Source: 2022 Switzerland IMO TST, Problem 6
Tags: Integers, number theory, Divisibility
07.08.2022 18:42
$n|n^2+4^n+7^n\Rightarrow n|4^n+7^n\Rightarrow (n,4)=(n,7)=1$ Let $p$ be the least prime divisor of $n\Rightarrow p\notin \{2,7\},4^n\equiv (-7)^n\mod p$ $\Rightarrow\exists a\in\mathbb{Z}:-7a\equiv 1\mod p\Rightarrow (4a)^n\equiv (-7a)^n\equiv 1\mod p\Rightarrow (4a)^{ (n,p-1)}\equiv 1\mod p$ Since $p$ is the least prime divisor of $n$, we have $(n,p-1)=1\Rightarrow 4a\equiv 1\equiv -7a\mod p\Rightarrow p|11a\Rightarrow p=11\Rightarrow 11|n$ Using LTE lemma, we have $v_{11}(4^n+7^n)=1+v_{11}(n)$. Besides, $v_{11}(n^2)=2v_{11}(n)=2v_{11}(n)\Rightarrow v_{11}(n^2+4^n+7^n)\geq\min(1+v_{11}(n),2v_{11}(n))\geq v_{11}(n)+1\Rightarrow$ Q.E.D.
07.08.2022 18:45
Is it possible to solve with this method? I'm not getting anywhere. Firstly, we rewrite the expression as $n + \frac{4^n+7^n}{n}$. The numerator of the second term will always be odd, so for the expression to be an integer $n$ must also be odd. Thus, $4^n+7^n \equiv 0 \pmod 11$. If $n$ is prime (and we know $n \neq 2$), we will always have $4^n \equiv 4 \pmod n$ and $7^n \equiv 7 \pmod n$, so $4^n+7^n \equiv 11 \pmod n$ for prime $n$. Thus, if $n$ is prime, the only way $\frac{4^n+7^n}{n}$ can be an integer is if $n = 11$. Next, assume $n$ is nonprime. For some integer $p$, if $\frac{4^n+7^n}{n}$ is an integer, we will have $4^n+7^n = p \cdot n$, or $pn \equiv 0 \pmod {11}$. We now split into cases. Case 1: $n \equiv 0 \pmod {11}$. Case 2: $p \equiv 0 \pmod {11}$.
08.08.2022 00:58
OlympusHero wrote: Is it possible to solve with this method? I'm not getting anywhere. Firstly, we rewrite the expression as $n + \frac{4^n+7^n}{n}$. The numerator of the second term will always be odd, so for the expression to be an integer $n$ must also be odd. Thus, $4^n+7^n \equiv 0 \pmod 11$. If $n$ is prime (and we know $n \neq 2$), we will always have $4^n \equiv 4 \pmod n$ and $7^n \equiv 7 \pmod n$, so $4^n+7^n \equiv 11 \pmod n$ for prime $n$. Thus, if $n$ is prime, the only way $\frac{4^n+7^n}{n}$ can be an integer is if $n = 11$. Next, assume $n$ is nonprime. For some integer $p$, if $\frac{4^n+7^n}{n}$ is an integer, we will have $4^n+7^n = p \cdot n$, or $pn \equiv 0 \pmod {11}$. We now split into cases. Case 1: $n \equiv 0 \pmod {11}$. Case 2: $p \equiv 0 \pmod {11}$. I think your cases are wrong. Case $1$ should be $n \equiv 0 \pmod{11}$ and then you use the LTE lemma to notice that if $n = a \cdot 11^k$ with $v_{11}(n) = k$, then $v_{11}(4^n + 7^n) = v_{11}(n) + 1 = k+1$, implying that when studying $\pmod {11^{k+1}}$, you get that $p \equiv 0 \pmod {11}$. Case $2$ is $n \not\equiv 11$ directly implying $p \equiv 0 \pmod {11}$ as $4^n + 7^n \equiv 0 \pmod {11}$. This is basically kevin_06's solution. It's pretty optimal I would say.
11.10.2024 20:27
Bruh, isn't this too easy for a TST? Note that \( n \mid 4^n + 7^n \). Let \( q \) be the smallest prime divisor of \( n \). We have \[ 4^n \equiv -7^n \pmod{q} \implies \left( \frac{4}{7} \right)^n \equiv -1 \pmod{q} \implies \left( \frac{4}{7} \right)^{2n} \equiv 1 \pmod{q}. \]This implies that \( \text{ord}_q\left( \frac{4}{7} \right) \mid \gcd(2n, q-1) = 2 \), and since it's not 1, we have \( 16 \equiv 49 \pmod{q} \). Therefore, \( q = 3 \) or \( q = 11 \). If \( q = 3 \), then \( 4 \equiv 7 \pmod{3} \), a contradiction. Hence, \( q = 11 \). Note that \( n \) is even, else \( 2 \mid 7^n \), which is not possible. Thus, \( n \) must be odd. We have \[ v_{11}\left( \frac{4^n + 7^n}{n} \right) = 1 + v_{11}(n) - v_{11}(n) = 1, \]so \( 11 \mid \frac{4^n + 7^n}{n} \), and since \( 11 \mid n \), we are done.