Sayılar Teorisi
Bölme
\begin{align*}
&a\mid b \Rightarrow~~\exists \ k\in\mathbb{I}~~~~b=ka \\
&a\nmid b
\end{align*} Teoremler
1)
\begin{align*}
&a\mid b \wedge a\mid c \Rightarrow a\mid(b+c)\\
&b=s.a~~~~c=t.a\\
&b+c=s.a+t.a \\
&b+c=(s+t)a
\end{align*}2)
a\mid b \Rightarrow \forall_c \in \mathbb{I}~~~~a\mid(b.c)3)
\begin{align*}
&a \mid b \wedge b\mid c \Rightarrow a\mid c\\
&b=s.a~~c=t.b\\
&c=(t.s)a
\end{align*}Bölme İşlemi
a \in \mathbb{I}~~~~\exists d\in \mathbb{N}^+\\
a=dq+r\wedge 0\leq r< d -7=-3.3+2~~bu~kurala~uymuyor \\ -7=-2.3-1~~\checkmark \\ 8=3.2+2~~\checkmark
Modül Aritmetiği
Modül İşlemi
m\in \mathbb{N}^+~~a,b\in \mathbb{I} \\
r=a(mod~m) \Leftrightarrow a=q.m+r \wedge 0\leq r < m\\
\begin{align*}
0 < a < m & \Rightarrow r=a \wedge q=0 \\
a=m & \Rightarrow r=0 \wedge q=1 \\
a=q.m & \Rightarrow r=0 \wedge q=\frac{a}{m}
\end{align*}(a~mod~m)mod~m=a
Modül Denkliği
a(mod~m)=b(mod~m)=r\\ a=q_a.m+r\\ b=q_b.m+r
a-q_a.m=b-q_b.m\\ (a-b)=(q_a-q_b)m\\ m\mid (a-b)\\ a=b(mod~m)~~~~c=d(mod~m)\\ (a+c)=(b+d)\\ (a.c)=(b.d)
Asal Sayı
p\rightarrow asaldır\\
p>1\\
\neg(\exists q(q\in \{2,3,4,\ldots,p-1\} \wedge q \mid p))OBEB (GCD)
B=\{x\mid a \wedge x \mid b \} \\\begin{align*}
x=OBEB(a,b) =~&max~\alpha\\
OBEB(a,b) =~&gcd(a,b)\\
&gcd(a,b) = 1
\end{align*}a ile b aralarında asal demektir.
OKEK (LCM)
ab=gcd(a,b).lcm(a,b)
Öklid Algoritmasıyla GCD Hesabı
Yardımcı Teorem:
a=b.q+r\\ gcd(a,b)=d~olsun\\ gcd(b,r)=d'~olsun\\ d=d'
d \mid a \wedge d \mid b \Rightarrow d\mid (-q.b) \Rightarrow d \mid (a-q.b) \Rightarrow d\mid r
gcd(a,b)=cd(b,r) < gcd(b,r) \\ d' \mid b \wedge d'\mid r \Rightarrow d' \mid q.b \wedge d' \mid r\\ \Rightarrow d' \mid (g.b+r) \Rightarrow d' \mid a
gcd(b,r) = cd(a,b) \leq gcd(a,b)
Euclidean algorithm
a=b.q_1+r\\ a=r_0 ~~ b=r_1 ~~ r =r_2
\begin{aligned}
r_0 &= r_1.q_1+r_2 \wedge ~ 0 \leq r_2 < r_1 \rightarrow gcd(r_0,r_1) \\
r_1 &= r_2.q_2+r_3 \wedge ~ 0 \leq r_3 < r_2 \rightarrow gcd(r_1,r_2) \\
r_2 &= r_3.q_3+r_4 \wedge ~ 0 \leq r_4 < r_3 \rightarrow gcd(r_2,r_3) \\
\vdots \\
r_{n-2} &= r_{n-1}.q_{n-1}+r_n \wedge ~ 0 \leq r_2 < r_1 \rightarrow gcd(r_{n-2},r_{n-1}) \\
r_{n-1} &= r_n.q_n+0 \wedge ~ 0 \leq r_2 < r_1 \rightarrow gcd(r_{n-1},r_n) \\
r_n &= 0.q_n+0 \wedge ~ 0 \leq r_2 < r_1 \rightarrow gcd(r_n,0) = r_n\\
\end{aligned}
Örnek
gcd(3,5)
5=1.3+2 ~~~~ gcd(3,5) \\ 3=1.2+1 ~~~~ gcd(2,3) \\ 2=2.1+0 ~~~~ gcd(1,2) \\ gcd(1,0)
func gcd(n,m)
if m=0 then gcdi = n
else gcd(m, n(mod m))örnek
gcd(252,198)=?
\begin{align*}
292 &= 1.198 + 54 \\
198 &= 3.54 + 35 \\
54 &= 1.36 + 18 \\
36 &= 2.18 + 0
\end{align*}Cebirin Temel Teoremi
gcd(n,m) = t.n + s.m
18 = gcd(252,198) = t252+s198
\begin{align*}
292=1.198 + 54 &\rightarrow 54=252-1.198 \\
198=3.54 + 36 &\rightarrow 36 =198-3.54 \\
54=1.36 + 18 &\rightarrow 18 = 54-1.36 \\
36=2.18 + 0 &
\end{align*}\begin{align*}
18&=54-1.36\\
&=54-1.(198-3.54) \\
&=1.54-1.198+3.54 \\
&=4.54 -1.198 \\
&=4.(252-1.198) - 1.198 \\
&=4.252-4.198-1.198\\
&=4.252-5.198
\end{align*}Örnek
gcd(3,5)
\begin{align*}
5=1.3+2 &\rightarrow 2=5-1.3 \\
3=1.2+1 &\rightarrow 1=3-1.2 \\
2=2.1+0 &
\end{align*}\begin{align*}
1&=3-1.2\\
&=1.3-1.(5-1.3) \\
&=1.3-1.5+1.3 \\
&=2.3-1.5
\end{align*}
Extended Euclid
g=gcd(n,m) = t.n+u.m
gcdext(n,m,g,t,u)
if m=0 then g=n, t=1, u=0
else
si=u
ui=t-floor(n/m).u
ti=s
end{gcdext}Örnek
\begin{align*}
&gcdext(5,3,g,t,u) \rightarrow g=1~~t=-1~~u=2 \\
&gcdext(3,2,g,t,u) \rightarrow g=1~~t=1~~u=-1 \\
&gcdext(2,1,g,t,u) \rightarrow g=1~~t=0~~u=1 \\
&gcdext(1,0,g,t,u) \rightarrow g=1~~t=1~~u=0 \\
\end{align*}Örnek
\begin{align*}
gcdext(87,55,g,t,u) &\rightarrow g=1~~t=-12~~u=19 \\
gcdext55,32,g,t,u) &\rightarrow g=1~~t=7~~~~~~~u=-12 \\
gcdext(32,23,g,t,u) &\rightarrow g=1~~t=-5~~~~u=7 \\
gcdext(23,9,g,t,u) &\rightarrow g=1~~t=2~~~~~~~u=-5 \\
gcdext(9,5,g,t,u) &\rightarrow g=1~~t=-1~~~~u=2 \\
gcdext(5,4,g,t,u) &\rightarrow g=1~~t=1~~~~~~~u=-1 \\
gcdext(4,1,g,t,u) &\rightarrow g=1~~t=0~~~~~~~u=1 \\
gcdext(1,0,g,t,u) &\rightarrow g=1~~t=1~~~~~~~u=0 \\
\end{align*}Ödev
extended euclid algoritmasını implemente ediniz
// C++ program to demonstrate working of
// extended Euclidean Algorithm
#include <bits/stdc++.h>
using namespace std;
// Function for extended Euclidean Algorithm
int gcdExtended(int a, int b, int *x, int *y)
{
// Base Case
if (a == 0)
{
*x = 0;
*y = 1;
return b;
}
int x1, y1; // To store results of recursive call
int gcd = gcdExtended(b%a, a, &x1, &y1);
// Update x and y using results of
// recursive call
*x = y1 - (b/a) * x1;
*y = x1;
return gcd;
}
// Driver Code
int main()
{
int x, y, a = 35, b = 15;
int g = gcdExtended(a, b, &x, &y);
cout << "GCD(" << a << ", " << b
<< ") = " << g << endl;
return 0;
}
Leave a Reply