Problem archive/om/_76.1.3.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% Szablon LaTeX do rozwiązań zadań z Olimpiady Matematycznej %%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass{article}
\usepackage[utf8]{inputenc}

% Tutaj można zmienić grubość marginesu.
\usepackage[left=2cm, top=2cm, right=2cm, bottom=1cm, includeheadfoot, headheight=50pt, a4paper]{geometry}
\usepackage{polski}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{amsmath}
\usepackage{amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Możesz dodać pakiety %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\usepackage{nazwa_pakietu}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Uzupełnij swoje dane %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\imieNazwisko}{Hostek}
\newcommand{\email}{email}
\newcommand{\nrzad}{3}

% Tutaj jest numeracja stron
\pagestyle{fancy}

\fancyhf{}
\lhead{\fontsize{12}{16}\selectfont
\noindent
\imieNazwisko\\
\email \\}
\chead{
\fontsize{16}{22}\selectfont
\textbf{Zadanie \nrzad}}
\cfoot{
Strona $\thepage$ z $\pageref{LastPage}$
}

\renewcommand{\headrulewidth}{0pt}
\begin{document}
\fontsize{17}{16}\selectfont
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% A tu jest tekst rozwiązania %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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\))

\hfill\break\indent
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\)

\hfill\break\indent
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}\).

\hfill\break\indent
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\).

\hfill\break\indent
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}\).

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

\end{document}