Problem OM 76.1.3

Treść zadania

Dana jest dodatnia liczba całkowita $n$ będąca iloczynem 2024 parami różnych liczb pierwszych. Wyznaczyć liczbę dodatnich liczb całkowitych $k$ spełniających równość $$n + \gcd(n, k) = k$$

Rozwiązanie

Rozpiszmy kilka podstawowych obserwacji:

Po pierwsze, zauważmy, że $\gcd(n,k)$ jest dodatnie, a zatem musi być: $k > n$. Przeto, skoro $k > n$, to możemy zapisać $k$ jako $k = n + a$, gdzie $a \in \mathbb{Z^+}$.
Po drugie, zauważmy, że $\gcd(n,k)\in \left< 1, n \right>$

Z tych obserwacji możemy przekształcić nasz problem na problem równoważny, gdzie zamiast szukać $k\in\mathbb{Z^+}$ spełniających $n + \gcd(n, k) = k$, szukamy $a\in\mathbb{Z^+} , a \leq n $ spełniających $\gcd(n,n+a)=a$.

Korzystając z algorytmu Euclidesa do liczenia $\gcd$ mamy, że $\gcd(n,n+a) = \gcd(n,a)$.

Rozpatrzmy, przeto, dwa przypadki:

$a$ jest dzielnikiem $n$
$a$ nie jest dzielnikiem $n$

W pierwszym przypadku, skoro $a$ jest dzielnikiem $n$ to z definicji $\gcd$ mamy, że $\gcd(n,a)=a$, a to jest właśnie to czego szukamy.

Pozostaje teraz (dla tego przypadku) po prostu zliczyć liczbę dzielników $n$. Z twierdzenia o liczbie dzielników wiadomo, że jest ich $2^{2024}$.

W drugim przypadku, skoro $a$ nie jest dzielnikiem $n$, to z definicji $\gcd$ mamy, że $\gcd(n,a)=1$, więc jedynym kandydatem jest $1$, ale nie może być, ponieważ $1$ jest dzielnikiem $n$, a w tym przypadku rozważamy jedynie $a$, które nie są dzielnikiem $n$. A więc w tym przypadku nie mamy żadnej liczby $a$ spełniającej równość $\gcd(n,n+a)=a$.

Podsumowując, rozpatrzając dwa przypadki wiemy, że wszystkich $a$, które spełniają $\gcd(n,n+a) = a$ jest $2^{2024}$. A skoro szukanie liczby liczb $a$ spełniających $\gcd(n,n+a) = a$ jest równoważne szukaniu liczby liczb $k$ spełniających $n + \gcd(n, k) = k$, to stąd wiemy, że liczba takich liczb $k$ jest równa $2^{2024}$.

Odp.: Liczba dodatnich liczb całkowitych $k$ spełniających równość $n + \gcd(n, k) = k$ jest $2^{2024}$.

% NumberTheory, Divisors, GCD, Primes

\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, etap 1, zadanie 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}

\section*{Treść zadania}

Dana jest dodatnia liczba całkowita $n$ będąca iloczynem 2024 parami
różnych liczb pierwszych. Wyznaczyć liczbę dodatnich liczb całkowitych $k$
spełniających równość
$$n + \gcd(n, k) = k$$

\bigskip

\section*{Rozwiązanie}

Rozpiszmy kilka podstawowych obserwacji:
\begin{enumerate}
    \item Po pierwsze, zauważmy, że \(\gcd(n,k)\) jest dodatnie, a zatem musi być: \(k > n\). Przeto, skoro \(k > n\), to możemy zapisać \(k\) jako \(k = n + a\), gdzie \(a \in \mathbb{Z^+}\).
    \item Po drugie, zauważmy, że \(\gcd(n,k)\in \left< 1, n \right>\)
\end{enumerate}

Z tych obserwacji możemy przekształcić nasz problem na problem równoważny, gdzie zamiast szukać \(k\in\mathbb{Z^+}\) spełniających \(n + \gcd(n, k) = k\), szukamy \(a\in\mathbb{Z^+} , a \leq n \) spełniających \(\gcd(n,n+a)=a\).

Korzystając z algorytmu Euclidesa do liczenia \(\gcd\) mamy, że \(\gcd(n,n+a) = \gcd(n,a)\).

Rozpatrzmy, przeto, dwa przypadki: 

\begin{enumerate}
    \item \(a\) jest dzielnikiem \(n\)    
    \item \(a\) nie jest dzielnikiem \(n\)
\end{enumerate}

W pierwszym przypadku, skoro \(a\) jest dzielnikiem $n$ to z definicji \(\gcd\) mamy, że \(\gcd(n,a)=a\), a to jest właśnie to czego szukamy.

Pozostaje teraz (dla tego przypadku) po prostu zliczyć liczbę dzielników \(n\). Z twierdzenia o liczbie dzielników wiadomo, że jest ich \(2^{2024}\).

W drugim przypadku, skoro \(a\) nie jest dzielnikiem $n$, to z definicji \(\gcd\) mamy, że \(\gcd(n,a)=1\), więc jedynym kandydatem jest \(1\), ale nie może być, ponieważ \(1\) jest dzielnikiem \(n\), a w tym przypadku rozważamy jedynie \(a\), które nie są dzielnikiem \(n\). A więc w tym przypadku nie mamy żadnej liczby \(a\) spełniającej równość \(\gcd(n,n+a)=a\).

Podsumowując, rozpatrzając dwa przypadki wiemy, że wszystkich \(a\), które spełniają \(\gcd(n,n+a) = a\) jest \(2^{2024}\). A skoro szukanie liczby liczb \(a\) spełniających \(\gcd(n,n+a) = a\) jest równoważne szukaniu liczby liczb \(k\) spełniających \(n + \gcd(n, k) = k\), to stąd wiemy, że liczba takich liczb \(k\) jest równa \(2^{2024}\).

\textbf{Odp.:} Liczba dodatnich liczb całkowitych \(k\) spełniających równość \(n + \gcd(n, k) = k\) jest \(2^{2024}\).

\end{document}