1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
% Document MUST be built with XeLaTeX!
\documentclass[11pt,a4paper]{article}
\usepackage[margin=1.5cm]{geometry}
% Поддръжка на български език
% Thanks to https://tex.stackexchange.com/a/136926
\usepackage{fontspec}
\defaultfontfeatures{Ligatures=TeX}
\setmainfont{CMU Serif}
\setsansfont{CMU Sans Serif}
\usepackage[bulgarian,english]{babel}
\usepackage{amsmath} % Математически символи
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{amsfonts} % Още математически символи
\usepackage{cancel} % Зачертаване
\usepackage[dvipsnames]{xcolor} % Цветни кутийки + допълнителни цветове
\usepackage{indentfirst} % Индентация на параграф след секция
\usepackage{enumitem}
\setlist[enumerate]{label=\arabic*.}
\renewcommand{\thesection}{}
\let\oldforall\forall
\renewcommand{\forall}{\; \oldforall}
\let\oldexist\exists
\renewcommand{\exists}{\; \oldexist}
\usepackage[pdfauthor={Камен Димитров Младенов, КН Летен семестър, 2023},
pdftitle={Домашна работа 2 по А2, Зад 1},
pdfsubject={},
pdfkeywords={},
colorlinks=true,
urlcolor=blue]{hyperref}
\title{\vspace{-1.5cm}Домашно №2, Задача 1 по Алгебра 2 на Компютърни Науки}
\author{Камен Димитров Младенов, Група 6}
\date{12 Май 2023}
\begin{document}
\maketitle
\section{Решение}
Търсим $n$, за което $\exists ! a,b \in \mathbb{Z}_n \setminus \{0,1\}: ab \equiv 0 \; (\mod n)$, тоест $a$ и $b$ са (единствените) такива, че $ab = 0 + kn = kn$ за някое $k \in \mathbb{Z}$.
Допълнително премахваме $1$, понеже ако б.о.о. $a = 1$, то $ab = 1b = b \neq kn$ за всяко $k$ и $n$.
Ако $n$ е просто, няма делители на нулата, понеже ако представим двете страни на $ab=kn$ като умножения на прости числа, няма как лявата страна да съдържа $n$ (и няма как да има равенство).
Нека фиксираме най-малките прости числа $c,d \in \{2, ..., n-1\}$, които удовлетворяват $n = c.d$.
Тогава със сигурност ще имаме поне един делител на нулата, при $a=c$ и $b=d$, $ab = cd = n$.
За всяко $1 < k < n$, за което можем да представим б.о.о. $a$ като $c.k \in \mathbb{Z}_n \setminus \{0,1\}$, $ab$ ще бъде "нов" различен делител на нулата: $ab = c.k.d = k.cd = kn \neq n$.
Тоест, искаме за всяко такова $k$ и всяко $z \in \mathbb{Z}_n \setminus \{0, 1\}$, $k.z \notin \mathbb{Z}_n \setminus \{0,1\}$.
Най-малките им възможни стойности са $k = 2 = z$, тоест искаме $kz = 4 \notin \mathbb{Z}_n$, значи $n \in \{1, ..., 4\}$.
За $n = 1$ и $n = 2$, $\mathbb{Z}_n \setminus \{0,1\} = \emptyset$, за $n = 3$, няма делител на нулата.
Следователно, отговорът е $n = 4$.
\end{document}
|
