The triplet of positive integers $(a,b,c)$ with $a<b<c$ is called a fatal triplet if there exist three nonzero integers $p,q,r$ which satisfy the equation $a^p b^q c^r = 1$. As an example, $(2,3,12)$ is a fatal triplet since $2^2 \cdot 3^1 \cdot (12)^{-1} = 1$. The positive integer $N$ is called fatal if there exists a fatal triplet $(a,b,c)$ satisfying $N=a+b+c$. (a) Prove that 16 is not fatal. (b) Prove that all integers bigger than 16 which are not an integer multiple of 6 are fatal.
Problem
Source: Indonesian National Mathematical Olympiad 2024, Problem 2
Tags: number theory, Inamo, primes, factorizations, Indonesia, NT construction, Indonesia MO
Furra
28.08.2024 10:22
Solution from the proposer (me):
Assume otherwise, and $16=a+b+c$. Any prime that divides at least one of $a$, $b$, and $c$ should divide at least one of the other variables. We may discount $11$ and $13$.
If 7 is part of the primes, then $a+b+c>7+14=21$, contradiction. If $5$ is part of the primes, then the only possible tuplets $(a,b,c)=(1,5,10)$, is not fatal.
Thus, $a,b,c\in \{1,2,3,4,6,8,9,12\}$.
Also, from parity, $a$, $b$, $c$ must all be even. Hence, the only possible tuplets are $(a,b,c)=(2,6,8)$, which is not fatal. QED.
We work with modulo 6 and 4. We have:
\begin{align*}
&6k+2=2+2k+4k, \quad 2^1(2k)^1(4k)^{-1}=1,\\
&6k+4=4+2k+4k,\quad 4^1(2k)^2(4k)^{-2}=1,\\
&4k+3=3+k+3k,\quad 3^1(k)^1(3k)^{-1}=1,\\
&4k+9=9+k+3k\quad 9^1(k)^2(3k)^{-2}=1.
\end{align*}Each of these decomposition can be easily seen as fatal.
The only remaining cases are $N=21,45$ (from the case $4k+9$, with $k=3$ or $k=9$). We have \begin{align*}
&21=1+4+16=3+6+12, \quad 1^14^216^{-1}=3^16^{-2}12^1=1, \\
&45=6+12+27=3+12+24, \quad 6^6 12^{-3} 27^1 = 9^1 12^{6}24^{-4}=1.
\end{align*}This completes the proof.
To be fair, analysing the parities directly provides shorter proof...
The original question asked to find largest $N$ with $6\not|N$ such that $N$ is not fatal.
The name is chosen from... this. Watch Oshi no Ko thx.
The structure of this problem is inspired from multiplicatively dependent vectors of algebraic numbers. While reading through this paper, I misread the "vectors of maximal rank" definition as "no nonzero exponents" instead of "nonzero vectors of exponents"; thus, this question was born.
I still don't know what would happen if $6|N$.
Mufara07
28.08.2024 11:05
Furra wrote: Solution from the proposer (me):
Assume otherwise, and $16=a+b+c$. Any prime that divides at least one of $a$, $b$, and $c$ should divide at least one of the other variables. We may discount $11$ and $13$.
If 7 is part of the primes, then $a+b+c>7+14=21$, contradiction. If $5$ is part of the primes, then the only possible tuplets $(a,b,c)=(1,5,10)$, is not fatal.
Thus, $a,b,c\in \{1,2,3,4,6,8,9,12\}$.
Also, from parity, $a$, $b$, $c$ must all be even. Hence, the only possible tuplets are $(a,b,c)=(2,6,8)$, which is not fatal. QED.
We work with modulo 6 and 4. We have:
\begin{align*}
&6k+2=2+2k+4k, \quad 2^1(2k)^1(4k)^{-1}=1,\\
&6k+4=4+2k+4k,\quad 4^1(2k)^2(4k)^{-2}=1,\\
&4k+3=3+k+3k,\quad 3^1(k)^1(3k)^{-1}=1,\\
&4k+9=9+k+3k\quad 9^1(k)^2(3k)^{-2}=1.
\end{align*}Each of these decomposition can be easily seen as fatal.
The only remaining cases are $N=21,45$ (from the case $4k+9$, with $k=3$ or $k=9$). We have \begin{align*}
&21=1+4+16=3+6+12, \quad 1^14^216^{-1}=3^16^{-2}12^1=1, \\
&45=6+12+27=3+12+24, \quad 6^6 12^{-3} 27^1 = 9^1 12^{6}24^{-4}=1.
\end{align*}This completes the proof.
To be fair, analysing the parities directly provides shorter proof...
The original question asked to find largest $N$ with $6\not|N$ such that $N$ is not fatal.
The name is chosen from... this. Watch Oshi no Ko thx.
The structure of this problem is inspired from multiplicatively dependent vectors of algebraic numbers. While reading through this paper, I misread the "vectors of maximal rank" definition as "no nonzero exponents" instead of "nonzero vectors of exponents"; thus, this question was born.
I still don't know what would happen if $6|N$.
So that's why they played that video at the end Hold up how did modulo 4 get in here
Mufara07
28.08.2024 11:34
Nevermind, I can see why from caseworking on $6k + i$, $\forall$ $ i=1,3,5$