Problem archive/om/76.1.3-en.tex

\fontsize{13}{16}\selectfont

Problem Statement

Let $ n $ be a positive integer that is the product of 2024 pairwise distinct prime numbers. Determine the number of positive integers $ k $ satisfying the equality $$n + \gcd(n, k) = k.$$

Solution:

Let $ n $ be a positive integer that is the product of 2024 pairwise distinct prime numbers. Determine the number of positive integers $ k $ satisfying the equality $ n + \gcd(n, k) = k $. (Note: $\gcd$ denotes the greatest common divisor.)

\break\indent We begin with several key observations:

First, note that $ \gcd(n,k) $ is positive, which implies $ k > n $. Thus, we can write $ k $ as $ k = n + a $, where $ a \in \mathbb{Z^+} $.
Second, observe that $ \gcd(n,k) \in \left\{ 1, 2, \ldots, n \right\} $.

From these observations, we can reformulate the problem: instead of seeking $ k \in \mathbb{Z^+} $ satisfying $ n + \gcd(n, k) = k $, we now seek $ a \in \mathbb{Z^+} $ with $ a \leq n $ that satisfy $ \gcd(n, n+a) = a $.

Using the Euclidean algorithm for computing $ \gcd $, we have $ \gcd(n, n+a) = \gcd(n, a) $.

We consider two cases:

1) $ a $ is a divisor of $ n $

2) $ a $ is not a divisor of $ n $

\break\indent In the first case, since $ a $ is a divisor of $ n $, the definition of $ \gcd $ implies $ \gcd(n, a) = a $, which satisfies our requirement.

It remains to count the number of divisors of $ n $. By the divisor function theorem, there are $ 2^{2024} $ such divisors.

\break\indent In the second case, since $ a $ is not a divisor of $ n $, the definition of $ \gcd $ implies $ \gcd(n, a) = 1 $. However, this would require $ a = 1 $, but $ 1 $ is a divisor of $ n $, contradicting the assumption. Thus, there are no such $ a $ in this case.

\break\indent In summary, combining both cases, the number of $ a $ satisfying $ \gcd(n, n+a) = a $ is $ 2^{2024} $. Since finding such $ a $ is equivalent to finding $ k $ satisfying $ n + \gcd(n, k) = k $, the number of such $ k $ is $ 2^{2024} $.

\break\indent Answer: The number of positive integers $ k $ satisfying the equality $ n + \gcd(n, k) = k $ is $ 2^{2024} $.

% NumberTheory, Divisors, GCD, Primes, English

\documentclass[a4paper,12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{fancyhdr}
\usepackage{lastpage} 
% \usepackage{polski}
\usepackage{fontspec}
\setmainfont{Linux Libertine O}

\usepackage[left=2cm, top=2cm, right=2cm, bottom=1cm, includeheadfoot, headheight=50pt, a4paper]{geometry}

\newcommand{\Name}{Hostek}                
\newcommand{\Email}{your.email@example.com}   
\newcommand{\ProblemNumber}{LXXVI OM, stage 1, problem 3}               

\pagestyle{fancy}
\fancyhf{} 
\fancyhead[L]{\Name \\ \Email}
\fancyhead[C]{\ProblemNumber}
\fancyfoot[C]{\thepage/\pageref{LastPage}}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\begin{document}
\fontsize{13}{16}\selectfont


\section*{Problem Statement}

Let \( n \) be a positive integer that is the product of 2024 pairwise distinct prime numbers. Determine the number of positive integers \( k \) satisfying the equality
$$n + \gcd(n, k) = k.$$

\bigskip

\noindent\textbf{Solution:}

Let \( n \) be a positive integer that is the product of 2024 pairwise distinct prime numbers. Determine the number of positive integers \( k \) satisfying the equality
\( n + \gcd(n, k) = k \). (\textbf{Note:} \(\gcd\) denotes the greatest common divisor.)

\hfill\break\indent
We begin with several key observations:
\begin{enumerate}
    \item First, note that \( \gcd(n,k) \) is positive, which implies \( k > n \). Thus, we can write \( k \) as \( k = n + a \), where \( a \in \mathbb{Z^+} \).
    \item Second, observe that \( \gcd(n,k) \in \left\{ 1, 2, \ldots, n \right\} \).
\end{enumerate}

From these observations, we can reformulate the problem: instead of seeking \( k \in \mathbb{Z^+} \) satisfying \( n + \gcd(n, k) = k \), we now seek \( a \in \mathbb{Z^+} \) with \( a \leq n \) that satisfy \( \gcd(n, n+a) = a \).

Using the Euclidean algorithm for computing \( \gcd \), we have \( \gcd(n, n+a) = \gcd(n, a) \).

We consider two cases:

\noindent
1) \( a \) is a divisor of \( n \)

\noindent
2) \( a \) is not a divisor of \( n \)

\hfill\break\indent
In the first case, since \( a \) is a divisor of \( n \), the definition of \( \gcd \) implies \( \gcd(n, a) = a \), which satisfies our requirement.

It remains to count the number of divisors of \( n \). By the divisor function theorem, there are \( 2^{2024} \) such divisors.

\hfill\break\indent
In the second case, since \( a \) is not a divisor of \( n \), the definition of \( \gcd \) implies \( \gcd(n, a) = 1 \). However, this would require \( a = 1 \), but \( 1 \) is a divisor of \( n \), contradicting the assumption. Thus, there are no such \( a \) in this case.

\hfill\break\indent
In summary, combining both cases, the number of \( a \) satisfying \( \gcd(n, n+a) = a \) is \( 2^{2024} \). Since finding such \( a \) is equivalent to finding \( k \) satisfying \( n + \gcd(n, k) = k \), the number of such \( k \) is \( 2^{2024} \).

\hfill\break\indent
Answer: The number of positive integers \( k \) satisfying the equality \( n + \gcd(n, k) = k \) is \( 2^{2024} \).

\end{document}