2014 Antalya Matematik Olimpiyatı Soru 14

[matematikolimpiyati]

$S=\{1,2,3,...,999,1000\}$  kümesindeki sayılardan kaç tanesi  $n=7^{999!}-5^{999!}$  farkını böler?

$\textbf{a)}\ 518  \qquad\textbf{b)}\ 624  \qquad\textbf{c)}\ 686  \qquad\textbf{d)}\ 720  \qquad\textbf{e)}\ 735$

[Metin Can Aydemir]

Cevap: $\boxed{C}$

$m\in S$ olsun. Eğer $7\mid m$ veya $5\mid m$ ise $5\nmid n$ ve $7\nmid n$ olduğundan $m\nmid n$ olacaktır. Eğer $(m,5)=(m,7)=1$ ise $\phi(m)\mid 999!$ olduğundan Euler teoreminden $m\mid n$ bulunur. Yani $S$'nin $5$'e veya $7$'e bölünmeyen elemanlarına bakmalıyız. $$S_5=\{5,10,15,\dots,1000\}\implies |S_5|=200$$ $$S_7=\{7,14,21,\dots,994\}\implies |S_7|=142$$ $$S_{35}=\{35,70,105,\dots, 980\}\implies |S_{35}|=28$$ olduğundan aradığımız elemanların sayısı $$1000-200-142+28=686$$ bulunur.