0
$\begingroup$

Define a sequence $a_n$ as follows: for each positive integer $n$, set $a_n$ equal to the remainder of $n^n$ when it is divided by 101. What is the smallest positive integer $d$ such that $a_n = a_{n+d}$ for all $n$?

I have a feeling perhaps this would have to deal with orders, as a number raised to the order of it modulo $101$ would be congruent to the number added to it's order, still modulo $101$. However, I don't know how to go about this, as the powers change with terms.

Can someone provide me with a solution? Thanks so much :)

$\endgroup$
2
$\begingroup$

$d$ must be a multiple of $101$ because $101$ is prime. Otherwise, $101-d$ is not a multiple of $101$, so $a_{101-d}\not=0$, while $a_{101}=0$.

Now, write $d=101k$. Consider $a_{n+d}\equiv(n+d)^{n+d}\equiv n^{n+101k}=n^nn^{101k}\pmod{101}$. Therefore, we must guarantee that $n^{101k}=(n^{101})^k\equiv 1\pmod{101}$.

Using Fermat's little theorem, we know that $n^{101}\equiv n\pmod{101}$. Therefore, we must conclude that $n^k\equiv 1\pmod{101}$.

Finally, since $101$ is prime, $\mathbb{Z}/101^\times\simeq\mathbb{Z}/100$, so there is an element of (multiplicative) order $100$. Let $g$ be that element of order $100$, then we know that $k\geq 100$, but by Fermat's little theorem, $k=100$ is enough.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.