Geomania.Org Forumları
Fantezi Cebir => Sayılar Teorisi => Konuyu başlatan: Metin Can Aydemir - Mart 01, 2025, 03:42:17 ös
-
$\phi(1775)=1400$ olduğundan, Euler teoreminden, her $(x,1775)=1$ için $x^{1400}\equiv 1\pmod{1775}$ olacaktır.
Problem: Her $(x,1775)=1$ için $x^{n}\equiv 1\pmod{1775}$ olmasını sağlayan en küçük pozitif $n$ tamsayısı kaçtır?
-
Euler teoreminden daha iyisi, Çin kalan teoremi + Euler teoremidir. Bundan daha iyisi de mertebeyi hesaplamaktır ama çoğu zaman mertebe hesabının da güçlükleri vardır. Çarpımsal mertebe'nin tanınımdan dolayı, mertebe'den daha iyisi yoktur ;D .
$1775 = 5^2\cdot 71$ olduğundan $x^n \equiv 1 \pmod{25}$ ve $x^n \equiv 1 \pmod{71}$ denkliklerini sağlayan en küçük $n$ pozitif tam sayılarını bulup ekok'unu almalıyız. Elbette bu en küçük sayılar mertebedir. Euler teoreminden $\phi (25) = 20$ ve $\phi(71) = 70$ olduğundan $n = \text{ekok}(20,70)=140$ bulunur. Bu sayı bir $x$ için mertebe oldu mu bilmiyoruz henüz.
Daha küçük bir $n$ olmadığını göstermek için modülo 25 ve modülo 71 içinde uygun bir $x$ primitif kökünün olduğunu da göstermek gerekir. Bu kısmını da Metin Can'a havale ediyorum ;D
-
Daha küçük bir $n$ olmadığını göstermek için modülo 25 ve modülo 71 içinde uygun bir $x$ primitif kökünün olduğunu da göstermek gerekir. Bu kısmını da Metin Can'a havale ediyorum ;D
Primitif kök teoremi zaten $25$ ve $71$ modunda primitif kök olduğunu söylüyor. Çin kalan teoreminden hem $25$ modunda hem de $71$ modunda primitif olacak şekilde bir $x$ tamsayısı vardır. $x^{140}\equiv 1\pmod{1775}$ olduğunu zaten Lokman hocam ispatladı. Eğer $x^n\equiv 1\pmod{1775}$ ve $n\leq 140$ ise $$x^n\equiv 1\pmod{25}\implies 20\mid n$$ $$x^n\equiv 1\pmod{71}\implies 70\mid n$$ olacağından $140\mid n$'dir. Buradan da $n=140$ bulunur. Yani mertebesi $1775$ modunda $140$ olan bir tamsayı vardır.
Bu sayıyı direkt bulmamı istiyorsanız, elle denemek veya bilgisayara sormak lazım. Ben sordum, $25$ modundaki primitif kök $2$, $71$ modundaki primitif kök ise $7$'ymiş. Yani $1427$ sayının $1775$ modundaki mertebesi $140$'dır.
Euler teoreminden daha iyisi, Çin kalan teoremi + Euler teoremidir. Bundan daha iyisi de mertebeyi hesaplamaktır ama çoğu zaman mertebe hesabının da güçlükleri vardır. Çarpımsal mertebe'nin tanınımdan dolayı, mertebe'den daha iyisi yoktur ;D .
O zaman şöyle bir soru sorayım;
Problem: Her $(x,1088)=1$ için $x^n\equiv 1\pmod{1088}$ olmasını sağlayan en küçük pozitif $n$ tamsayısı kaçtır?