Gönderen Konu: 899 ile bölümden kalan  (Okunma sayısı 250 defa)

Çevrimdışı Lokman Gökçe

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3332
  • Karma: +22/-0
  • İstanbul
899 ile bölümden kalan
« : Nisan 25, 2022, 04:29:10 ös »

Soru (Lokman GÖKÇE): $1\leq n \leq 899$ ve $(n, 899) = 1$ koşulunu sağlayan $n$ tam sayılarının çarpımının $899$ ile bölümünden kalan kaçtır?
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1956
  • Karma: +8/-0
Ynt: 899 ile bölümden kalan
« Yanıtla #1 : Nisan 27, 2022, 03:00:20 öö »
$899 = 29 \cdot 31$.
$\varphi (n) = 28 \cdot 30 = 840$.
Her $n$ sayısına karşılık $nm \equiv 1 \pmod {899}$ olacak şekilde bir $m$ sayısı vardır.
$n=m$ olan, yani $n^2 \equiv 1 \pmod {899}$ denkliğini sağlayan $n$ sayısı $2k$ olsun. ($n \not \equiv -n \pmod {899}$ ve her $n$ çözümüne karşılık $-n$ de bir çözüm olacağı için)
$\varphi (n) - 2k = 840-2k$ kadar sayının çarpımı $\bmod {899}$ da $1$ e denk olacaktır.
Diğer sayılar için $n\cdot (-n) \equiv -1 \pmod {899}$ olacağı için aradığımız cevap $(-1)^k$ olacaktır.
$x^2 \equiv 1 \pmod {899}$ denkliğinin çözüm sayısı, $$\begin{array}{rcrrllcrr}
x & \equiv & 1 & \pmod {29} & \qquad \text{ve} \qquad & x & \equiv & 1 & \pmod {31}
\\ x & \equiv & -1 & \pmod {29} & \qquad \text{ve} \qquad & x & \equiv &  -1 & \pmod {31}
\\ x & \equiv & 1 & \pmod {29} & \qquad \text{ve} \qquad & x & \equiv & -1 & \pmod {31}
\\ x & \equiv & -1 & \pmod {29} & \qquad \text{ve} \qquad & x & \equiv & 1 & \pmod {31}
\end{array}$$ Çinlilerin Kalan Teoremi gereğince (her bir denklik sistemi için $\bmod {899}$ da bir tane olacağı için) toplam $2k = 4$ tanedir. ($1, 30, 869, 898$)
Bu durumda aradığımız yanıt $(-1)^k = 1$ olacaktır.

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1956
  • Karma: +8/-0
Ynt: 899 ile bölümden kalan
« Yanıtla #2 : Nisan 27, 2022, 03:55:11 öö »
Aradığımız çarpım,
$$A = \dfrac{1\cdot 2 \cdots (31-1)}{29} \cdot
 \dfrac{32\cdot 33 \cdots (2\cdot 31 -1)}{2\cdot 29} \cdots
 \dfrac{869\cdot 870 \cdots (29\cdot 31 -1)}{30 \cdot 29}
$$ şeklinde yazılabilir.$\bmod{31}$ de incelediğimizde $$A \equiv \dfrac{(30!)^{29}}{30! \cdot 29^{30}} \pmod {31}$$ elde ederiz. Wilson Teoremini ve Fermat'ın Küçük Teoremini uyguladığımızda $$A \equiv \dfrac{(-1)^{28}}{1} \equiv 1 \pmod {31} \tag {1}$$ elde ederiz.

Benzer şekilde $$A = 1 \cdots (29-1) \cdot
 \dfrac{30 \cdots (2\cdot 29 -1)}{31} \cdots
 \dfrac{842 \cdots (30\cdot 29 -1)}{28\cdot 31} \cdot
871 \cdots (31\cdot 29 -1)
$$ şeklinde yazılabilir. $$A \equiv \dfrac{(28!)^{31}}{28! \cdot 31^{28}} \equiv  \dfrac{(-1)^{30}}{1} \equiv 1 \pmod {29} \tag{2}$$
Buradan $A\equiv 1 \pmod{899}$ elde edilir.
« Son Düzenleme: Nisan 27, 2022, 03:56:50 öö Gönderen: geo »

Çevrimdışı Metin Can Aydemir

  • G.O Genel Moderator
  • Geo-Maniac
  • ********
  • İleti: 667
  • Karma: +8/-0
Ynt: 899 ile bölümden kalan
« Yanıtla #3 : Nisan 27, 2022, 10:00:16 öö »
Soruyu genelleştirelim. $m\geq 2$ sayısı için $1\leq n\leq m$ ve $(m,n)=1$ olan $n$ sayılarının çarpımına $f(m)$ dersek, geo hocamın ilk gönderisindeki mantığı kullanarak $f(m)$ sayısının $m$ modunda $1$ veya $-1$ kalanı vereceğini görebiliriz. Peki ne zaman hangi kalanı vereceğini bulabilir miyiz? Gauss'un Wilson teoremi genelleştirmesine göre eğer $m$ sayısı ilkel köke sahipse cevap $-1$'dir, aksi takdirde $1$'dir. Bu genelleştirmemin bir yönünü ispatlayalım.

Varsayalım ki $m$ sayısının ilkel kökü olsun. $m=2$ ise genelleştirmenin sağlandığı görülebilir. $m>2$ için $r$ bir ilkel kök olsun. O halde, $1\leq n\leq m$ ve $(m,n)=1$ şartlarını sağlayan her $n$ sayısı için $n\equiv r^{k_n}\pmod{m}$ olacak şekilde bir $1\leq k_n\leq \phi(m)$ sayısı vardır. Dolayısıyla $$f(m)\equiv r^{1+2+\cdots+\phi(m)}\equiv r^{\frac{\phi(m)(\phi(m)+1)}{2}}\equiv \left(r^{\frac{\phi(m)}{2}}\right)^{\phi(m)+1}\equiv (-1)^{\phi(m)+1}\pmod{m}$$ olacaktır çünkü $r$ bir ilkel köktür ve $r^{\frac{\phi(m)}{2}}$ sayısı $1$ kalanı veremez ($\phi(m)$ sayısının çift olduğu formülünden görülebilir). Ayrıca $\phi(m)+1$ tek sayıdır. Dolayısıyla $$f(m)\equiv (-1)^{\phi(m)+1}\equiv -1\pmod{m}$$

Peki $m$ modunda ilkel kök yoksa neden $1$ kalanı verir? Bunu okuyucuya bırakıyorum.
Gerçek hikayeler aslında söylenmeyenlerdir.

Çevrimdışı Lokman Gökçe

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3332
  • Karma: +22/-0
  • İstanbul
Ynt: 899 ile bölümden kalan
« Yanıtla #4 : Nisan 27, 2022, 10:36:50 ös »
Elinize sağlık arkadaşlar, güzel çözümleriniz ve açıklamalarınız için teşekkürler. Benim çözümümde de Çin kalan teoremi ve çarpımsal tersi kendine eşit sayıları kullanma üzerinedir.
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

 


Sitemap 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 
SimplePortal 2.3.3 © 2008-2010, SimplePortal