Problem OM 76.1.3

\fontsize{13}{16}\selectfont

Problem Statement

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 + NWD(n, k) = k.$$

Solution:

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$. (Tutaj: $gcd$ to $nwd$)

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:

1) $a$ jest dzielnikiem $n$

2) $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}
\fontsize{13}{16}\selectfont


\section*{Problem Statement}

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 + NWD(n, k) = k.$$

\bigskip

\noindent\textbf{Solution:}

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\). (\textbf{Tutaj:} \(gcd\) to \(nwd\))

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: 

\noindent
1) \(a\) jest dzielnikiem \(n\)

\noindent
2) \(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}\).

\end{document}