Tübitak Lise 1. Aşama 1996 Soru 13

[matematikolimpiyati]

$1 \leq a \leq 100$  olmak üzere$,\ a^{60} \equiv 1 \pmod{77}$

bağıntısını sağlayan kaç tane $a$  tam sayısı vardır?

$\textbf{a)}\ 79  \qquad\textbf{b)}\ 78  \qquad\textbf{c)}\ 77  \qquad\textbf{d)}\ 76  \qquad\textbf{e)}\ 75$

[geo]

Yanıt: $\boxed B$

Euler'e göre $(a, 77)=1$ olmak üzere her $a$ tam sayısı için $a^{\phi (77)} \equiv a^{60} \equiv 1 \pmod {77}$.
$[1,100]$ aralığında $77$ ile aralarında asal olan sayıların sayısı $100 - \left \lfloor \dfrac {100}7 \right \rfloor -  \left \lfloor \dfrac {100}{11} \right \rfloor +   \left \lfloor \dfrac {100}{77} \right \rfloor = 78$.