899 ile bölümden kalan

[Lokman Gökçe]

• Tweet

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?

[geo]

• Tweet

$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.

[geo]

• Tweet

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.

[Metin Can Aydemir]

• Tweet

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.

[Lokman Gökçe]

• Tweet

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.