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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .