13
$\begingroup$

Before anyone comments, yes this is kind of a duplicate of Prove that $1989\mid n^{n^{n^{n}}} - n^{n^{n}}$ . The problem that I'm having I don't see the $n=5$ as a counterexample. Also if anyone wants to know where I got this problem from here.

I'm looking at the problem $\color{red} {\text{A10}}$. This is not a homework. This is a question I chose to do for fun and I'm totally not sure how to do this problem after playing with for hours. I have made a conjecture that I cannot prove. I believe $n^n \equiv k \mod 1989$ while $n^{n^n} \equiv k \mod 1989$ while $n^{n^{n^n}}\equiv k \mod 1989$ for integer $n \ge 4$. Anyways right now I'm just looking for a hint. I still want to try. You can put spoilers in your answers if you want to. Also we can use whatever we want to prove this. Though I do warn you my number theory skills are still a work in progress. And what I'm looking for is to prove this: $1989 \mid n^{n^{n^{n}}} - n^{n^{n}}$ for integer $n \ge 3$

$\endgroup$
6
  • 2
    $\begingroup$ $n=5$ is not a counterexample. $\endgroup$ May 19, 2015 at 3:35
  • $\begingroup$ I agree Ross . Also @anon $k$ is an integer. For example. $5^5 \equiv 1136 , 5^{5^5} \equiv 1136, 5^{5^{5^5}} \equiv 1136$ all mod 1989. $\endgroup$
    – randomgirl
    May 19, 2015 at 3:38
  • $\begingroup$ So then say $n^n\equiv n^{n^n}\equiv n^{n^{n^n}}$ mod $1989$ to communicate your conjecture. $\endgroup$
    – anon
    May 19, 2015 at 3:39
  • $\begingroup$ Right. I just wrote it like a system of equations just in case there was someway to do this with that Chinese theorem. $\endgroup$
    – randomgirl
    May 19, 2015 at 3:40
  • 1
    $\begingroup$ @randomgirl: I don't think math110's answer is conclusive yet until he addresses a month-old comment/counter-example. $\endgroup$ Jul 31, 2015 at 14:14

2 Answers 2

4
$\begingroup$

Lemma 1 $$ \forall n \in \mathbb{N}_{>0} \hspace{1.5em} n^{n^n} \equiv n^n \pmod3 $$

This is trivial.

Lemma 2 $$\forall n \in \mathbb{N} \hspace{1.5em} n\ge 3 \implies n^{n^n} \equiv n^n \pmod{16} $$

Proof. If $n$ is even, then $n\ge4$ and thus $16 \mid n^n, n^{n^n}$. If $n$ is congruent to $\pm 1$ modulo $16$, the proposition above holds. Then, we only need to check $\pm 3, \pm 5, \pm 7$. By Euler's theorem, \begin{align} n\equiv 3 \pmod{16} \implies 3^{n^n} - 3^n &\equiv 3^{n^n-n \pmod8}-1 \\ &\equiv 3^{3^{n\pmod4}-3}-1 \\ &\equiv 3^{3\cdot 8} -1 \equiv 0 \pmod{16} \end{align} \begin{align} n\equiv 5 \pmod{16} \implies 5^{n^n} - 5^n &\equiv 5^{n^n-n \pmod8}-1 \\ &\equiv 5^{5^{n\pmod4}-5}-1 \equiv 0 \pmod{16} \end{align} \begin{align} n\equiv 7 \pmod{16} \implies 7^{n^n} - 7^n &\equiv 7^{n^n-n \pmod8}-1 \\ &\equiv 7^{7^{n\pmod4}+1}-1 \\ &\equiv 7^{7^3+1} -1 \equiv 7^{43\cdot 8} -1 \equiv 0 \pmod{16} \end{align} The cases $-3,-5,-7$ are now trivial.

Theorem $$\forall n \in \mathbb{N} \hspace{1.5em} n\ge 3 \implies n^{n^{n^n}} \equiv n^{n^n} \pmod{1989} $$

Proof. We first split the congruence as follows. $$\begin{align} n^{n^{n^n}} \equiv n^{n^n} \pmod{1989} &\iff \begin{cases} n^{n^{n^n}} \equiv n^{n^n} \pmod{9} \\ n^{n^{n^n}} \equiv n^{n^n} \pmod{13} \\ n^{n^{n^n}} \equiv n^{n^n} \pmod{17} \end{cases} \end{align}$$ Since $2,2,3$ are primitive roots of $9,13,17$ respectively, then $$\begin{align} n^{n^{n^n}} \equiv n^{n^n} \pmod{9} &\iff \begin{cases} n^{n^n}\cdot\operatorname{ind}_2n \equiv n^n\cdot\operatorname{ind}_2n \pmod{6} & 3 \nmid n \\ 0 \equiv 0 & 3 \mid n\end{cases} \\[1ex] n^{n^{n^n}} \equiv n^{n^n} \pmod{13} &\iff \begin{cases} n^{n^n}\cdot \operatorname{ind}_2n \equiv n^n \cdot\operatorname{ind}_2n \pmod{12} & 13 \nmid n \\ 0 \equiv 0 & 13 \mid n\end{cases} \\[1ex] n^{n^{n^n}} \equiv n^{n^n} \pmod{17} &\iff \begin{cases} n^{n^n}\cdot \operatorname{ind}_3n \equiv n^n \cdot\operatorname{ind}_3n \pmod{16} & 17 \nmid n \\ 0 \equiv 0 & 17 \mid n\end{cases} \end{align}$$ By the lemmas, these congruences hold for all $n\ge 3$.

$\endgroup$
0
0
$\begingroup$

Note $1989=3^2\cdot 13\cdot 17$. Use Euler's theorem (a.k.a. Euler's totient theorem), namely, let $\varphi(n)$ be the totient function, then,

$$a^{\varphi(n)} \equiv 1 (\text{mod}\, n)$$

for all $a$ relatively prime to $n$. We then have the following result: $$m|n^a-n^b\Longleftrightarrow \varphi(m)|(a-b),\;\rm{gcd}(n,m)=1\tag1$$ Since $\rm{lcm}[\varphi(3^2),\varphi(13),\varphi(17)]=2^4\cdot 3$, so we only prove $$2^4 \cdot3|(n^{n^n}-n^n)$$ and $\rm{lcm}[\varphi(2^4),\varphi(3)]=8$ we only prove $$8|n^n-n$$ where $n$ is odd. It is clear.

$\endgroup$
4
  • 2
    $\begingroup$ No, $m\mid n^a-n^b\iff \text{ord}_m (n)\mid a-b$, but $\text{ord}_m (n)$ is not necessarily equal to $\varphi(m)$ when $(n,m)=1$. E.g. obviously $m\mid 1^a-1^b$ for any $a,b,m$, but we don't always have $\varphi(m)\mid a-b$. Another example: $5\mid 4^4-4^2$, but we don't have $5\mid 4-2$. $\endgroup$
    – user26486
    Jun 10, 2015 at 21:12
  • $\begingroup$ As mentioned above $n=4,m=5,a=4,b=2$ is a counter-example to your first claim. $\endgroup$
    – Winther
    Jul 31, 2015 at 7:23
  • $\begingroup$ @math110: I've filled in some details of your post, but you need to clarify your claim $(1)$ since user26486 pointed out a counter-example. Otherwise, this answer doesn't seem to be conclusive yet. $\endgroup$ Jul 31, 2015 at 14:43
  • 1
    $\begingroup$ @TitoPiezasIII I have unaccepted this answer. I had put this question on the back burner for a long time. I think it was a question I wasn't really prepared for, didn't have the proper background. If you can offer a better solution, I will accept it. $\endgroup$
    – randomgirl
    Jul 31, 2015 at 18:43

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.