Find all positive integers $n$ such that $9^{n}-1$ is divisible by $7^n$.
Problem
Source:
Tags: induction, function, modular arithmetic, Divisibility Theory
22.07.2007 05:44
nicetry007 wrote: $ 9^{n}-1 = (3^{n}+1)(3^{n}-1)$. This implies that $ 7$ either divides $ 3^{n}+1$ or $ 3^{n}-1$ and not both. Hence, $ 7^{n}$ either divides $ 3^{n}+1$ or $ 3^{n}-1$ and not both. But $ 0 \;< \;3^{n}-1 \;<\;3^{n}+1 \;< \; 7^{n}$. Hence, $ 7^{n}$ does not divide $ 3^{n}+1$ or $ 3^{n}-1$, which implies that $ 7^{n}$ does not divide $ 9^{n}-1$.
27.10.2007 04:21
An other lemma : Let $ p$ is a odd prime. Call order of a mod p is d where $ a\not\in\{ - 1,1\}$ Suppose $ a^d\equiv 1(\mod p^{k_0})$ Then the order of a $ \mod p^k$ is d for $ k = 1,...,k_0$ and $ d{p^{k - k_0}}$ if $ k > d$ It is an useful lemma and prove by induction on k by Newton express. Now consider our problem: $ ord_{9}(\mod 7) = 3$ and $ 9^3\equiv 1 (\mod 7 )$ Imply that $ ord_{9}(\mod 7^n) = {3}.{7^{n - 1}}$ Imply that $ 3.{7^{n - 1}}|n$ so has no positive integer satisfy the condition. Consider the equation: $ a^n\equiv 1 (\mod p^n)$ where $ a\not \in \{ - 1,1\}$ Prove that the equation has only solution. Here is some example : 1. Consider the function :$ f: N\to N$ Satisfy : $ \frac {n}{f(n)}$ is bound for all $ n\in N$ Consider the equation: $ a^n\equiv 1 (\mod p^{f(n)})$ Prove that the equation has finite solution.
12.08.2013 10:24
Very nice solution by nicetry007 which is likely the intended solution. Again, like A87, lifting the exponent kills this problem. Since $9^n-1\equiv 0\pmod{7}$ we notice $\text{ord}_{7}9=3$ therefore $n\equiv 0\pmod{3}$. Therefore substitute $n=3k$ to give us $729^k-1$ is divisible by $7^{3k}$. By lifting the exponent $v_7(729^k-1)=v_7(729-1)+v_7(k)=1+v_7(k)\ge 3k$. However $v_7(k)\le k$ so therefore $k+1\ge 1+v_7(k)\ge 3k$ contradiction. There are no such $n$.
25.08.2016 03:19
I apologize to everyone for my solution being very similar to that of Binomial-theorem. First take care of $9^n\equiv 2^n$ is periodical in $(mod{7})$, $2,4,1,2,4,1,\dots$.Thus $n=3m(m\in \mathbb N),and 7^{3m}|9^{3m}-1=729^m-1$.$7\nmid 729, 7\nmid 1, 7|729-1$.By Lifting the Exponent Lemma,$v_7(729^m-1)=v_7(729-1)+v_7(m)=1+v_7(m)$.Let $m=7^kt(k\in \mathbb N_{0},7\nmid t)$.Then $3\cdot 7^k\le 3\cdot 7^kt\le 1+k$ which is absurd$(k\in \mathbb N_{0})$.Therefore there is no such $f$.$\blacksquare$