42
$\begingroup$

As is the question in the title, I am wishing to find all positive integers $n$ such that $3^n + 5^n$ is divisible by $n^2 - 1$.

I have so far shown both expressions are divisible by $8$ for odd $n\ge 3$ so trivially a solution is $n=3$. I'm not quite sure how to proceed now though. I have conjectured that the only solution is $n=3$ and have tried to prove it but have had little luck. Can anyone point me in the right direction? thanks

$\endgroup$
  • 2
    $\begingroup$ Numerical checks confirm it up to $240002$ $\endgroup$ – Tim Ratigan Dec 19 '13 at 0:41
  • 1
    $\begingroup$ Yeah. For even $n$, $6\mid n$ and for odd $n$, $n$ is of the form $3(8k+1)$. I confirmed it up to $240\,000$ and trivially extended it to $240\,002$. @IanMateus $\endgroup$ – Tim Ratigan Dec 19 '13 at 0:51
  • 4
    $\begingroup$ I'm going to sleep, but I'll leave with the thought that maybe the recurrence relation $$ 3^{n+2}+5^{n+2} = 8(3^{n+1}-5^{n+1})-15(3^n+5^n) $$ might help. $\endgroup$ – Tim Ratigan Dec 19 '13 at 0:55
  • 3
    $\begingroup$ I tested it numerically for $n=1,\ldots,10^6$, and only $n=3$ works. $\endgroup$ – Yiorgos S. Smyrlis Dec 19 '13 at 12:52
  • 2
    $\begingroup$ @YiorgosS.Smyrlis: your comment with all the numbers fell prey to the problem described in this question. This ended up messing up the formatting of all the other comments to this question. Remember not to have a block of 79 whitespace-free characters in comments or text. $\endgroup$ – robjohn Dec 19 '13 at 16:18
15
$\begingroup$

This is a community wiki answer to summarize the main results we've got for quick access. Feel free to edit and add more results. Theoretical achievements are here:

Result. $3\mid n$, by virtually everyone.

Result. $n\equiv 1\pmod 2$, and, thus, $n\equiv 3\pmod 6$, obtained by benh. See also the message on chat.

Result. if a prime $p$ divides $n^2-1$, then $p\equiv 2^k\pmod{15}$ for some $k$, obtained by benh.

Result. $n^2-1$ isn't divisible by $3, 5, 7, 11$. Obtained by Yiorgos S. Smyrlis.

Result. $n\equiv \pm 3\pmod 8$. Obtained by Tim Ratigan.

Result. combining the congruences, $n\equiv 3, 93 \pmod{120}$. See a proof here.

Result. Jack D'Aurizio was able to rule out $n\not\equiv \pm1\pmod p$ for every prime number $p>5$ for which $(3\cdot 5^{-1})$ has an odd order $\pmod{p}$ or an order divisible by $4$, see here. In combination with benh's result this gives that the smallest odd prime factor of $n^2-1$ is at least $19$.


Numerical checkings are given and updated in this part.

Result. Listing was able to verify by brute force that $n=3 \lor n>10^{12}$, extending the result by Tapio Rajala that $n=3 \lor n>10^{11}$.

Add your own result or someone else's. Please give proper credit and don't post the proofs here; link them instead. For further discussion, e.g. disproving or strengthening any claim, use this chatroom.


This turned out to be a long standing open problem. Needless to say, breakthroughs in this question will be very well rewarded. I don't want this question to stop here, so I'll offer a +100 bounty very soon. Keep the good work up!

$\endgroup$
  • $\begingroup$ My last result is superseeded by @behn's one: every prime divisor of $n^2-1$ must be $\equiv\{1,2,4,8\}\pmod{15}$. However, the last lines of my post show that $n\not\equiv\pm 1\pmod{17}$. $\endgroup$ – Jack D'Aurizio Dec 27 '13 at 2:39
  • 1
    $\begingroup$ @JackD'Aurizio should we remove it, then? If yes, feel free to do it. If not, you may edit the pertinent parts. $\endgroup$ – Ian Mateus Dec 27 '13 at 2:52
  • 1
    $\begingroup$ I removed "$n\pm 1$ cannot be prime", too, since it follows from the fact that $n$ is odd. $\endgroup$ – Jack D'Aurizio Dec 27 '13 at 3:02
  • $\begingroup$ I would like to point that by combining my result and @behn's one we get a sieve for identifying eventual prime factors of $n^2-1$: they are only $19,23,31,53,61,109,181,\ldots$, i.e. prime factors $\equiv\{1,2,4,8\}\pmod{15}$ of numbers of the form $5^{4k+2}-3^{4k+2}$. $\endgroup$ – Jack D'Aurizio Dec 27 '13 at 3:20
9
+50
$\begingroup$

I'd better make this an answer. This was asked on MO long ago. Nobody could do it. Kevin Buzzard wrote to Andreescu and found out that the authors of the book don't know how to finish the problem. I put an answer summarizing what we had, in basic language.

See

https://mathoverflow.net/questions/16341/on-polynomials-dividing-exponentials

$\endgroup$
  • $\begingroup$ Amazing story!! $\endgroup$ – Ian Mateus Dec 27 '13 at 4:26
  • $\begingroup$ However, it is interesting to notice that $n^2-1=r^2+rs+4s^2$ or $n^2-1=2r^2+rs+2s^2$, since $\mathbb{Q}(\sqrt{-15})$ has class number two. A side-problem is then to find all the triples $(r,s,n)$ such that $r^2+rs+4s^2-n^2=1$ or $2r^2+rs+2s^2-n^2=1$. $\endgroup$ – Jack D'Aurizio Dec 27 '13 at 4:31
  • $\begingroup$ @JackD'Aurizio, right. The reason we can say that solutions are, at least, rather rare, is that both $n+1$ and $n-1$ must be primitively represented by appropriate binary quadratic forms. $\endgroup$ – Will Jagy Dec 27 '13 at 4:42
  • $\begingroup$ @IanMateus, glad you saw this. $\endgroup$ – Will Jagy Dec 27 '13 at 4:44
  • $\begingroup$ It does not look so ugly, indeed, since $n^2-1=4r^2+rs+s^2$ is impossible $\pmod{3}$. We have only to solve $2r^2+rs+2s^2=n^2-1$, or $A^2+3B^2=2n^2-2$. $\endgroup$ – Jack D'Aurizio Dec 27 '13 at 4:47
3
$\begingroup$

[update 3] Error for even $m$ which are not only perfect powers of $2$. Section $5$ is not sufficient to prove for such $m$, especially eqn. $(5.3)$ and $(5.8)$ must be completed for that cases, then this affects $(5.4)$ and $(5.10)$ and the general conclusion. I hope I can cure that problem, otherwise I'll retract my claim here soon*[/update 3]*



[update 2] I've added the consideration of the primefactor $2$ and can now defend the statement, that $n=3$ is the only solution. See section 6. [/update]

[update]: It seems to me that I've solved the problem nearly completely, while some yet unconsidered minor details might allow a small finite set of (perhaps trivial) solutions.
I consider the problem in terms of a number $m=n+1$, proceed from assuming $m$ as prime, as product of two, then of three primenumbers and see that the arguments extend easily to any squarefree number with the same result in each step, that there is no such $m$ and the final conclusion:

  • No solution for $m=n+1$ an odd squarefree number.

I consider then $m=p^a$ being a perfect prime power with the same result:

  • No solution for $m=n+1$ an odd perfect prime power with only a single prime.

I added a more comprehensive and -hopefully- full proof as section 5 below which replace sections 1 to 4. For redundancy and explanativity I'll leave that sections for the moment until someone could confirm that the proof is valid.
[/update]

I don't want however add my result to the common-wiki list unless someone has gone thru for a check against errors.


0: Useful notations/definitions
I introduce some notations first which I've explained in a couple of answers here in MSE and also in MO (I'll give the links later).

  • Let $ \{a,p\} = m $ denote the exponent $m$ to which the primefactor $p$ occurs in the number $a$

  • Let $ [ a : p] = 0 $ if $p$ does not divide $a$ and $ [ a : p] = 1 $ if it does (which is also known as Iverson brackets)

  • Let $f(n) = 5^n-3^n $ and $g(n)= f(2n)/f(n) = 5^n+3^n$ for shortness of notation

  • Let $\lambda$ denote the order of the cyclic subgroup modulo a prime $p$ such that $ \{f(\lambda_p),p\}\ge 1 $ with $\lambda$ minimal. We know, that $ \lambda$ is equal to or a divisor of $p-1$, such that also $ p=1 + \lambda_p \cdot \gamma_p$ with some $\gamma_p$

  • Let $\alpha$ denote the exponent, to which that primefactor p occurs at $f(\lambda)$ such that $\{ f( \lambda) , p \}=\alpha \ge 1$

  • Let's use indices like $\lambda_p$,$\alpha_q$ if multiple primefactors like $p,q$ are involved.

In general, we can now write the exponent of some primefactor $p$ of the primefactorization as $$ \{ f(n),p \} = [n : \lambda]( \alpha + \{n , p \} ) \tag 1$$ (for the primefactor $2$ we have a small modification but which will not bother here since in our argumentation that primefactor does not play an important role)

Finally let uns consider the given problem in terms of $m=n+1$ instead of $n$. Then $n^2-1 = m(m-2)$ and we ask for solutions of
$$ m(m-2) | 5^{m-1} + 3^{m-1}$$ or shorter $$ g(m-1) = k \cdot m (m-2) \qquad \qquad \text{ with some } k \gt 0$$ In the following I reduce the question to the simpler problem to show, that not even $m$ itself can be a factor of $g(m-1)$ which is then sufficient for the original question, whether $m(m-2) $ can be a factor of $g(m-1)$


1) Let's assume $m$ is a single odd prime.
Thus let's write $p$ for $m$ where $ p\in \mathbb P$ . Then also $p=1 + \lambda_p \cdot \gamma_p$ and $f(p-1)=f(\gamma \cdot \lambda) $ is divisible by $p$ by the above (because of Fermat's little theorem), or explicitely $$\{f(\lambda_p \cdot \gamma_p),p \} \ge 1 \qquad \qquad \text{ by definition of } \lambda_p$$

We can complete our question with the equality $$ g(p-1) = f(2(p-1))/f(p-1) = 5^{p-1} + 3^{p-1} $$ as $$ \begin{eqnarray} \{ g(p-1) , p \} &=& \{ f(2(p-1)) , p \} - \{f(p-1),p\} \\ &=& \; [2(p-1) : \lambda_p](\alpha_p + \{ 2(p-1) , p \}) \\ & & - [p-1 : \lambda_p](\alpha_p + \{p-1,p \}) \end{eqnarray} \tag {1.1} $$

We can then algebraically manipulate: the braces-expressions in the right parentheses can be omitted, since $p$ cannot be a factor of $p-1$ and so we can collect the rhs expressions: $$ \begin{eqnarray} \{ g(p-1) , p \} &=& [2(p-1) : \lambda_p](\alpha_p + 0) - [p-1 : \lambda_p](\alpha_p + 0) \\ &=& ([2(p-1) : \lambda_p] - [p-1 : \lambda_p])(\alpha_p + 0) \\ &=& ([2(\gamma_p \cdot \lambda_p ) : \lambda_p] - [\gamma_p \cdot \lambda_p : \lambda_p])\alpha_p \\ &=& ( 1 - 1) \alpha_p \\ &=& 0 \end{eqnarray} \tag {1.2} $$ which means, that the primefactor $p$ does not occur in $g(p-1)$ and so

  • $g(n)$ cannot be divisible by $n^2-1$ if $m=n+1$ is prime.


2) Now let's look at numbers $m$ which consist of $2$ primefactors like $m = p \cdot q$ .

In simple extension of the previous equation $(2)$ we get now two determinations: one for the exponent of the primefactor $p$ and one for that of the primefactor $q$ :
$$ \begin{eqnarray} \{ g(pq-1) , p \} &=& [2(pq-1) : \lambda_p](\alpha_p + \{2(pq-1),p \}) - [pq-1 : \lambda_p](\alpha_p + \{pq-1,p \}) \\ \{ g(pq-1) , q \} &=& [2(pq-1) : \lambda_q](\alpha_q + \{2(pq-1),q \}) - [pq-1 : \lambda_q](\alpha_q + \{pq-1,q \}) \end{eqnarray} \tag {2.1} $$ Again we can omit the braces in the most-righthand factors, because neither can $p$ divide $pq-1$ nor can $q$, so we have the reduced (and already collected) expressions $$ \begin{eqnarray} \{ g(pq-1) , p \} &=& ([2(pq-1) : \lambda_p] - [pq-1 : \lambda_p])\alpha_p \\ \{ g(pq-1) , q \} &=& ([2(pq-1) : \lambda_q] - [pq-1 : \lambda_q])\alpha_q \end{eqnarray} \tag {2.2} $$

We look at the first row for the primefactor $p$. We expand the term $$ \begin{eqnarray} pq-1 &=& (\gamma_p \lambda_p+1)(\gamma_q \lambda_q+1)-1 \\ &=& \gamma_p \lambda_p \gamma_q \lambda_q + \gamma_q \lambda_q+\gamma_p \lambda_p \end{eqnarray} $$ and get for the first Iverson-bracket the longer expression $$ [2(\gamma_p \lambda_p \gamma_q \lambda_q + \gamma_q \lambda_q+\gamma_p \lambda_p) : \lambda_p] $$ which can obviously (by cancelling of the $\lambda_p$ summands) be reduced to $$ [2( \gamma_q \lambda_q) : \lambda_p] $$ which, when similarly applied to the other Iverson brackets lead to the final equations $$ \begin{eqnarray} \{ g(pq-1) , p \} &=& ([2 \gamma_q \lambda_q : \lambda_p] - [ \gamma_q \lambda_q : \lambda_p])\alpha_p \\ \{ g(pq-1) , q \} &=& ([2 \gamma_p \lambda_p : \lambda_q] - [ \gamma_p \lambda_p : \lambda_q])\alpha_q \end{eqnarray} \tag {2.3} $$ Now we seem to arrive at a situation which alludes to an infinite descent - but it is simpler. In order that the parentheses do not evaluate to zero, the $\lambda$-values must divide in the first Iverson bracket but not in the second and thus must have exactly as many factors $2$ as are present in the numerator of the first Iverson bracket.
So let's rewrite

  • $ \lambda_p = 2^a l_p $ and $ \gamma_p = 2^A g_p $
  • $ \lambda_q = 2^b l_q $ and $ \gamma_q = 2^B g_q $

where $g_q,l_q,g_p,l_p$ are odd and all exponents are nonnegative.

Then by the above argument it must be that the exponents of the primefactor $2$ must match $a = 1+b+B $ in order that the whole parenthese does not vanish.
At the same time we must have that $ b = 1+a+A $ and thus $a = 1+1+a+A+B $ or $A+B=-2$
But since all exponents must be nonnegative we have a contradiction!
Thus we can conclude:

  • also $ m$ of the form $m=pq$ cannot satisfy the equation and thus for $n+1 = pq$ with $p,q$ odd primes allow no solution.

3) Considering $m$ as a number with 3 different primefactors shows now also a general key for disproving any squarefree number for $m$.

We assume $m=pqr$ and begin with the 3 equations $$ \begin{eqnarray} \{ g(pqr-1) , p \} &=& [2(pqr-1) : \lambda_p](\alpha_p + \{2(pqr-1),p \}) - [pqr-1 : \lambda_p](\alpha_p + \{pqr-1,p \}) \\ \{ g(pqr-1) , q \} &=& [2(pqr-1) : \lambda_q](\alpha_q + \{2(pqr-1),q \}) - [pqr-1 : \lambda_q](\alpha_q + \{pqr-1,q \}) \\ \{ g(pqr-1) , r \} &=& [2(pqr-1) : \lambda_r ](\alpha_r + \{2(pqr-1),r \}) - [pqr-1 : \lambda_r ](\alpha_r + \{pqr-1,r \}) \end{eqnarray} \tag {3.1} $$ Completely analoguous to the previous steps from (2.1) to (2.2) we can reduce the braces and collect items. $$ \begin{eqnarray} \{ g(pqr-1) , p \} &=& ([2(pqr-1) : \lambda_p] - [pqr-1 : \lambda_p])\alpha_p \\ \{ g(pqr-1) , q \} &=& ([2(pqr-1) : \lambda_q] - [pqr-1 : \lambda_q])\alpha_q \\ \{ g(pqr-1) , r \} &=& ([2(pqr-1) : \lambda_r] - [pqr-1 : \lambda_r])\alpha_r \end{eqnarray} \tag {3.2} $$ Only the expression for the iverson-brackets change in a significant way; but this shows also the way how this generalizes. We get $$pqr-1 = (\gamma_p \lambda_p+1)(\gamma_q \lambda_q+1)(\gamma_r \lambda_r+1)-1 $$ and get for the first iverson-bracket after cancelling by the "denominator" $$ [ (\gamma_q \lambda_q+1)(\gamma_r \lambda_r+1)-1 : \lambda_p $$ The full expansion of the parenthese becomes tidier now (and even more when more primefactors are involved), but we can easily step to the next equation, that of the exponents of 2.
We rewrite similar like in section 2
$$ \begin{eqnarray} \gamma_p &=& 2^a g_p &\qquad& \lambda_p &=& 2^A l_p \\ \gamma_q &=& 2^b g_q &\qquad& \lambda_q &=& 2^B l_q \\ \gamma_r &=& 2^c g_r &\qquad& \lambda_r &=& 2^C l_r \end{eqnarray} \tag {3.3} $$

where again all new indeterminates are odd and all exponents are nonnegative.
The equations for the exponents of the $2$'s contain now $\min()$-expressions, we get $$\begin{eqnarray} a &=& 1 + \min(b,c) + \min(B,C) \\ b &=& 1 + \min(c,a) + \min(C,B) \\ c &=& 1 + \min(a,b) + \min(A,B) \end{eqnarray} \tag {3.4} $$ It suffices now to assume one of the indeterminates $a,b,c$ to be the minimal one, say $c$ to arrive at the contradiction; because if we assume $c$ to be the minimum, and $b$ the next greater number, then the expression $1+\min(a,b)$ requires $c \gt b$ which is then a contradiction. Because this problem is symmetric for all indeterminates this derivation shows, that

  • that for no sqquarefree $m$ there is a solution possible.

The result in terms of $n$ is

  • There is no solution for $n = pqr... - 1$ where $pqr...$ means any squarefree number.


4) The final step must then be to generalize to repeated primefactors.
4.1) The case of $m=p^a$ is easily handled:

$$ \begin{eqnarray} \{ g(p^a-1) , p \} &=& \{ f(2(p^a-1)) , p \} - \{f(p^a-1),p\} \\ &=& \; [2(p^a-1) : \lambda_p](\alpha_p + \{ 2(p^a-1) , p \}) \\ & & - [p^a-1 : \lambda_p](\alpha_p + \{p^a-1,p \}) \\ \end{eqnarray} \tag {4.1}$$ It can immediately be reduced to
$$ \{ g(p^a-1) , p \} =( [2(p^a-1) : \lambda_p] - [p^a-1 : \lambda_p])\alpha_p \tag {4.2}$$ Now, $p^a-1$ factors into $(p-1)h(p)$ where $h(p)$ is an integer expression. Writing that factorization we find that $$ \{ g(p^a-1) , p \} =( [2(p-1)h(p) : \lambda_p] - [(p-1)h(p) : \lambda_p])\alpha_p \tag {4.3} $$ where it is obvious, that the parenthese in the rhs evaluates to zero $$ \{ g(p^a-1) , p \} =( 1 - 1 )\alpha_p $$ because $(p-1)$ is divisible by $\lambda_p$ due to the definitions/observations above in both Iverson-brackets.
That means:
- There is no solution for $m$ being a perfect power of a single primefactor.

4.2) The cases of arbitrarily composed odd $m$

I've not yet done the further generalization but I think it is the same arguing which leads to the complete result, that
- No odd $m$ of any composition allows a solution
(where perhaps some (possibly trivial) exceptions might be existent)



5) Generalization to repeated primefactors and full proof.
Here I rewrite the sections 1 to 4 in a more compact form and complete the proof for any $m$. The strategy is the same as before: I reduce the problem to the simpler question whether $ m | g(m-1) $ and then show by comparision of the primefactors of $m$ with that of $g(m-1)$ that at least one of the primefactors of $m$ does not occur in $g(m-1)$ and thus $m$ cannot be a factor of $g(m-1)$.
For the sake of conciseness I reduce the notation of $\lambda$ and $\alpha$ of a prime of some index $k$ - say $p_k$ to $\lambda_k$ resp. $\gamma_k$ instead of $\lambda_{p_k}$ and $\gamma_{p_k}$ as it would be required by their definition.

For a general squarefree $m$ and one primefactor $p_k$ of $m$ we get the equation in the most general form: $$ \begin{eqnarray} \{g(m-1) , p_k \} &=& \;\; [2(m-1):\lambda_k](\alpha_k + \{2(m-1),p_k \})\\ & & -[ (m-1):\lambda_k](\alpha_k + \{ (m-1),p_k \}) \end{eqnarray} \\ \tag {5.1}$$ for every primefactor $p_k$ of $m$.

First of all, if $p$ is a primefactor of $m$ it cannot be one of $m-1$, so the braces $\{2(m-1),p_k\}$ and $\{m-1,p_k\}$ evaluate to zero and can be omitted. Thus we have for all primefactors $p_k$:
$$ \{g(m-1) , {p_k}\} = ([2(m-1):\lambda_k]-[m-1:\lambda_k])\alpha_k \tag{5.2} $$ and in all these equations the parentheses must simultanuously evaluate to $1$ to allow $ m | g(m-1) $. We shall see, that at least one of those conditions can not be satisfied and thus $g(m-1)$ cannot be divisible by $m$.

Step 1: the general proof for numbers $m$ which are squarefree:
To handle the Iverson-brackets (which contain the symbol $\lambda$ for the order of cyclic subgroup) we expand the primefactors $p_k$ to show their components $$ p_k = 1+ \lambda_k \cdot \gamma_k $$ and rewrite that Iverson-bracket expanded as
$$ [2(m-1):\lambda_k] = \left[ 2 \left(\prod_{j=1..z}(1+ \lambda_j \cdot \gamma_j) - 1\right):\lambda_k \right]$$ where we use $z$ for the number of distinct primefactors.

For the $k$'th primefactor this reduces (by cancellation of the factor in the product, which contains $\lambda_k$ itself) to the two Iverson-brackets $$ \begin{eqnarray} 1. &\quad &[2(m-1):\lambda_k] &=& \left[2 \left(\prod_{j=1..z,j \ne k}(1+ \lambda_j \cdot \gamma_j \right) - 1) :\lambda_k\right] \\ 2. &\quad & [ (m-1):\lambda_k] &=& \left[ \prod_{j=1..z,j \ne k}(1+ \lambda_j \cdot\gamma_j) - 1:\lambda_k \right] \end{eqnarray} \tag{5.3} $$

In order to have this two Iverson-brackets different to get the parenthese nonzero, $ \lambda_k$ must contain exactly as many powers of $2$ as its "numerator" in the first of the two equations. Clearly, the number $w_k$ of primefactors $2$ in $\prod_{j=1..z,j \ne k}(1+ \lambda_j \cdot \gamma_j) $ $$ w_k = \{( \prod_{j=1..z,j \ne k} (1+ \lambda_j \cdot \gamma_j)) - 1 ,2\} \tag{5.4} $$ is equal or even bigger than the number of primefactors $2$ in each single value $\lambda_j$ $$ w_k \ge \min_{j=1..z,j \ne k} ( \{\lambda_j ,2\} ) \tag{5.5} $$ In order to have the Iverson-brackets evaluate to different values for some primefactor $p_k$ we must have that $$ w_k < \{\lambda_k , 2 \} = w_k+1 \tag{5.6} $$ This condition gives us now a contradiction.
If we assume $k$ such that $\lambda_k$ is the smallest of all $\lambda_j$ then we have that it must also be satisfied that $$ \{\lambda_k , 2 \} = w_k+1 \gt \min_{j=1..z,j \ne k}( \{\lambda_j \cdot \gamma_j , 2 \} ) \tag{5.7} $$ and thus is bigger than at least one of the other $\lambda_j$. But then it is no more the smallest one - hence: contradiction! So we have proven:

  • For every squarefree $m$ at least one of its primefactors cannot occur in $g(m-1)$ .

Step 2: the general proof for numbers $m$ of any composition:
The same occurs, if in (5.1) we allow repeated primefactors, such that we get exponents: $$ [2(m-1):\lambda_k] = \left[2 \left(\prod_{j=1..z,j \ne k} (1+ \lambda_j \cdot \gamma_j)^{a_j}\right) - 1:\lambda_k \right] \tag{5.8} $$ $$ [ (m-1):\lambda_k] = \left[ \left(\prod_{j=1..z,j \ne k} (1+ \lambda_j \cdot \gamma_j)^{a_j}\right) - 1:\lambda_k \right] \tag{5.9} $$ Because the introduced exponents $a_j$can only increase the number of primefactors $2$ in the numerators of the iverson brackets, the number of them in the $\lambda_k$ - values must also increase: $$ w_k = \{( \prod_{j=1..z,j \ne k} (1+ \lambda_j \cdot \gamma_j)^{a_j}) - 1 , 2\} \\ \ge \min_{j=1..z,j \ne k}( \{\lambda_j \cdot \gamma_j ,2\}a_j ) \tag{5.10} $$ but still the condition must be satisfied $$ w_k \lt \{\lambda_k , 2 \} = w_k+1 \tag{5.11} $$ because every $\lambda_k$ must contain more primefactors $2$ than the minimum in the others. But this is impossible because then we had no $\lambda_k$ with the smallest number of primefactors $2$.

  • This proves that the assumption of the existence of any $m$ which might satisfy the initial equation is false for any primefactor-composition of $m$, and so no such $m$ exists.

  • Consequently no $n$ with $n=m-1$ exists and we have proved the OP's assertion that there is no solution to the problem.


6. For the primefactor 2

The multiplicity of the primefactor $2$ in general $f(n)$ follows that equation:
$$ \{f(n),2 \} = 1 + 2*[n:2] + \{n,2\} \tag {6.1}$$ such that we have for $g(n)$ $$ \begin{eqnarray} \{g(n),2\} &=& \{f(2n),2\} - \{f(n),2\} \\ &=& (1 + 2 \cdot [2n:2] + \{2n,2\}) - ((1 + 2 \cdot [n:2] + \{n,2\})) \\ &=& 1 + 2 + 1+\{n,2\} - 1 - 2 \cdot [n:2] - \{n,2\} \\ &=& 1+ 2 \cdot (1-[n:2]) \\ \{g(m-1),2\} &=& 1+ 2 \cdot (1-[m-1:2]) \\ &=& 1+ 2 \cdot [m:2] \\ \end{eqnarray} \tag{6.2}$$ This means, for odd $m$ we have $ \{g(m-1),2 \} = 1 $ and for even $m$ with $m =2^a \cdot \mu $ we have $ \{g(m-1),2 \} = 3 $.

Thus for to have $ m | g(m-1) $ we can have $m=2^3 = 8$. But now the OP is more restrictive - it requires $ m(m-2) | g(m-1)$ and thus $m$ can only equal $m=2^2=4$ and $$m(m-2)=2^2 \cdot 2^1 = 2^3 | g(m-1) \tag {6.3}$$
Because in section 5 I proved that we cannot have an odd primefactor in $m$ this is the only solution and the only solution in terms of $n$ is

  • $n=3$ is the only solution for $ n^2-1 | g(n) $ .
$\endgroup$
  • $\begingroup$ Hi, Gottfried. Printed out as seven jpegs. This will take a while. Will. $\endgroup$ – Will Jagy Jan 15 '14 at 18:36
  • $\begingroup$ @Will, I come with a compressed full argumentation as section 5. I'll leave at the moment the previous sections for redundancy/explanativity $\endgroup$ – Gottfried Helms Jan 15 '14 at 19:38
  • $\begingroup$ An older text where I introduced first that notation and "symbolic algebra" can be found here : go.helms-net.de/math/expdioph/CyclicSubgroups_work.pdf It is still somehow draft but I think it introduces nicely into the concept of this piece of "exponential-diaophantine algebra" and gives also a proof for formula (1) $\endgroup$ – Gottfried Helms Jan 15 '14 at 21:36
  • $\begingroup$ We have $76 \mid g(75)$, contrary to what you claim. I suspect what went wrong is that in Section $5$, you did not take into account that $m$ could be even, which affects your argument for odd $p_k$. $\endgroup$ – Ivan Loh Jan 16 '14 at 21:50
  • $\begingroup$ @Ivan : ahh, thank you for that information - it's true! Hmm - I was just rewriting that matter to make it shorter and more systematic. Now I've first to fix that hole, hope it's possible - I'll try. $\endgroup$ – Gottfried Helms Jan 16 '14 at 22:10
2
$\begingroup$

Not an answer, but a few considerations.

If $n+1$ is a prime then $3^{n}+5^n = 3^{p-1}+5^{p-1}\equiv 2\pmod{p}$ is not divisible by $n+1$. In a similar way if $n-1$ is a prime then $3^{n}+5^n = 3^{p+1}+5^{p+1}\equiv 34\pmod{p}$, so $p$ can be only $2$ or $17$.

Apart from specific-primes-hunting, one can also try to give a bound for the number of prime factors, or the greatest power of $2$ dividing $9m^2-1$ and $3^{3m}+5^{3m}$, hoping to get an inequality for any $m$ big enough. For istance, $\nu_2(3^n+5^n)$ is equal to $1$ when $n$ is even and is equal to $3$ when $n$ is odd. This gives $n\not\equiv\pm 1\pmod{8}$.

Moreover we have $n\not\equiv\pm 1\pmod{3}, n\not\equiv\pm 1\pmod{5}$. If $n\equiv\pm 1\pmod{p}$ for some $p>5$, we must have $$ 3^n + 5^n \equiv 0\pmod{p}, $$ so $$ \left(3\cdot 5^{-1}\right)^n \equiv -1 \pmod{p} $$ and the order of $3\cdot 5^{-1}\pmod{p}$ must be even, and an even divisor of $2n$. This gives the additional information that if $p\equiv -1\pmod{4}$ and $15$ is a square $\pmod{p}$, then $n\not\equiv\pm 1\pmod{p}$, so: $$ n\not\equiv \pm 1\pmod{3,5,7,8,11,43,59,67,71,103,119,127,\ldots} $$ and: $$ n\pm 1\neq p $$ for any odd prime number $p$. Very few $n$s survive to this sieve!

The first survival is $n=528=23^2-1$, however $17\mid(n^2-1)$ while $16\mid 528$, so $3^n+5^n\equiv 2\pmod{17}$.

The next survival is $n=900$. We have $n^2-1=17\cdot 29\cdot 31\cdot 53$, but since $n\equiv 4\pmod{16}$, we have $3^n+5^n\equiv 3^4+5^4\equiv 9\pmod{17}$.

The next survival is $n=1080$, for which $n^2-1=13\cdot 23\cdot 47\cdot 83$. However, since $12\mid n$, $3^n+5^n\equiv 2\pmod{13}$.

The next one is $n=1158$, for which $n^2-1=13\cdot 19\cdot 61\cdot 89$. Luckily, $13\mid 3^n+5^n$, but since $n\equiv 6\pmod{18}$, $3^n+5^n\equiv 3^6+5^6\equiv 14\pmod{19}$.

The next one is $n=1680$, for which $n^2-1=23\cdot 41^2\cdot 73$. $n\equiv 8\pmod{22}$ holds, and so $3^n+5^n\equiv -1\pmod{23}$. This is not a surprise, since $23\mid 3^n+5^n$ implies $11\mid n$.

Then comes $n=1818$, for which $n^2-1=17\cdot 23\cdot 79\cdot 107$. $11$ does not divide $n$, so $23$ cannot divide $3^n+5^n$.

We arrive at $n=1920$, for which $n^2-1=17\cdot 19\cdot 101\cdot 113$. Since $n$ is a multiple of sixteen, seventeen cannot divide $3^n+5^n$.

Going on, $n=1962$, $n^2-1= 13\cdot 37\cdot 53\cdot 151$. Twelve divides $n$, no way.

For the same reason, $n=2172,n=2508$ and $n=3132$ fall, too.

$n=2868$ falls because $19\mid n^2-1$ while $n\equiv 6\pmod{18}$.

It has become quite boring, but this considerations show that $n$ must be bigger than three thousand.

It is interesting to notice that if $n$ is even, $3^n+5^n$ is the sum of two coprime squares, so for every odd prime $p$ that divides $3^n+5^n$, $p\equiv 1\pmod{4}$. However, if $n$ is even $n^2-1\equiv -1\pmod{4}$, so there must be at least one prime divisor of $n^2-1$ that cannot belong to the set of prime divisors of $3^n+5^n$.

So we must have $n\equiv \pm 3\pmod{24}$, ruling out all the previous examples.

$n=3003$ almost survives to the new sieve. We have $n^2-1=2^3\cdot 19\cdot 79\cdot 751$, and $19\cdot79\mid 3^n+5^n$. However $n\equiv 3\pmod{750}$, and $3^3+5^3$ is too small to be divisible by $751$.

Another interesting phenomenon. In order to have $17\mid 3^n+5^n$, $n$ must be even, since the least $k$ such that $(3\cdot 5^{-1})^k\equiv -1\pmod{17}$ is $k=2$. Since $n$ is odd, we can introduce the sieve condition $n\not\equiv\pm 1\pmod{17}$. We can do this for every prime $p\equiv 1\pmod{4}$ for which the order of $(3\cdot 5^{-1})$ is a multiple of four.

$\endgroup$
  • $\begingroup$ Why the highest power of two possibly dividing $3^n+5^n$ is three? $\endgroup$ – Ian Mateus Dec 27 '13 at 0:22
  • $\begingroup$ Because if $n$ is even, $3^n+5^n\equiv2\pmod{4}$. Otherwise, $3^n+5^n=(3+5)(5^{n-1}-3\cdot 5^{n-2}+\ldots)$, where the second bracket is the sum of an odd number of odd terms. $\endgroup$ – Jack D'Aurizio Dec 27 '13 at 0:44
  • $\begingroup$ I think one important fact is that $n$ is odd. All your survivors are even, so you should consider implementing it in your analysis. $\endgroup$ – Ian Mateus Dec 27 '13 at 0:57
  • $\begingroup$ Also, I don't understand the part "the order of $3^{-1}5$ must be even". Why? $\endgroup$ – Ian Mateus Dec 27 '13 at 0:59
  • $\begingroup$ Because otherwise the residue class $-1$ does not belong to the powers of $5/3 \pmod{p}$. $\endgroup$ – Jack D'Aurizio Dec 27 '13 at 1:01
1
$\begingroup$

Here are a few necessary conditions on $n$ summarizing my statements from the chat:

  1. $n$ is odd.
  2. any prime factor $p\mid n^2-1$ is of the form $p \equiv 1,2,4,8 \mod 15$.
  3. $n \equiv 3,93 \mod 120$

proofs:

1)

It is clear that $3 \nmid 3^n+5^n$ and $5\nmid 3^n+5^n$. Thus $3\mid n$. Write $n = 3m$, then $$3^n+5^n \equiv 0 \mod n^2-1 \\\Rightarrow (3^{-1}5)^n \equiv -1 \mod 9m^2-1.$$ Suppose $n$ is even. Then $-1$ is a square mod $9m^2-1$, so every odd prime factor $p$ of $9m^2-1$ is $p\equiv 1 \mod 4$. But $9m^2-1 \equiv 3 \mod 4$ as $n$ is even, a contradiction.

2)

The inverse of $3$ is $3^{-1} \equiv 3m^2 \mod 9m^2-1$, so from the identity shown above we get $$(15m^2)^n \equiv -1 \mod 9m^2-1. \\ \Rightarrow (-15) \equiv (15)^{-n+1}m^{-2n} \mod 9m^2-1$$ As $n$ is odd by 1.) we see that for any odd prime $p$ dividing $9m^2-1$ the Legendre-symbol $$1 = \left( \frac{-15}{p} \right) = \left( \frac{-1}{p} \right)\left( \frac{3}{p} \right) \left( \frac{5}{p} \right) = \left( \frac{p}{3} \right)\left( \frac{p}{5} \right)$$ using the Quadratic Reciprocity Theorem. This shows $p \equiv 1,2,4,8 \mod 15$.

3)

By 2) $n^2-1 \equiv 1,2,4,8 \mod 15$ because these residues form a multiplicative subgroup. We already know $3\mid n$ showing $n\equiv 3 \mod 15$.

As $16 \nmid 3^n+5^n$, we know $8 \nmid n^2-1 =(n-1)(n+1)$ and 1) shows $n\equiv 3,5 \mod 8$. Chinese Remainder Theorem gives the result stated in 3).

$\endgroup$
  • $\begingroup$ In order to have $\left(\frac{p}{3}\right)=\left(\frac{3}{p}\right)$ you need $p\equiv 1\pmod{4}$ - but you know that every odd prime factor of $3^n+5^n$ have such a form only when $n$ is even - this is not the case, since $n$ must be odd. $\endgroup$ – Jack D'Aurizio Dec 27 '13 at 1:37
  • $\begingroup$ Yes, but $\left(\frac{p}{3}\right)=\left(\frac{3}{p}\right)(-1)^{(p-1)/2}=\left(\frac{3}{p}\right)\left(\frac{-1}{p}\right)$ so it's a cancellation. $\endgroup$ – benh Dec 27 '13 at 1:38
  • $\begingroup$ That's right, ok. But, still, if every prime factor bigger than $5$ of $n$ is $\equiv\{1,2,4,8\}\pmod{15}$, I cannot see why $n^2-1\equiv\{1,2,4,8\}\pmod{15}$. Take $n=19$, for example. $\endgroup$ – Jack D'Aurizio Dec 27 '13 at 1:43
  • 1
    $\begingroup$ 3 must divide $n$ and $n^2-1\pmod{15}$ must belong to $\{1,2,4,8\}$, so $n$ can be only $\{3,6,9\}\pmod{15}$. This gives that $n$ can be only $\{3,1,4\}\pmod{5}$, but if $n\equiv\pm 1\pmod{5}$ then $5\mid n^2-1$, so $n$ can be only $3\pmod{5}$. $\endgroup$ – Jack D'Aurizio Dec 27 '13 at 4:05
  • 1
    $\begingroup$ I am so happy that I wasn't wrong but just stupid :) Thank you very much!! $\endgroup$ – benh Dec 27 '13 at 4:08
0
$\begingroup$

EDIT: as pointed out in the comments, this is not correct. I'll leave the answer here for now in case someone finds a way to fix it.

By Fermat's little theorem, $a^n \equiv a \pmod{n}$, whenever $a$ and $n$ is coprime. Therefore $$3^n + 5^n \equiv 8 \pmod{n+1}.$$ But this must be congruent to $0$ since $n^2-1=(n+1)(n-1)$ and therefore also $n+1$ should divide the expression and so $$8 \equiv 0 \pmod{n+1}.$$ This only happens when $n=1$, $n=3$ or $n=7$. One can check the $n=7$ case by hand but we can also use the congruence for $n-1 = 6$ $$3^7 + 5^7 \equiv 3 + 5 \equiv 2 \not \equiv 0 \pmod{6}.$$

$\endgroup$
  • 6
    $\begingroup$ Fermat's Little Theorem only applies to prime $n$ $\endgroup$ – Tim Ratigan Dec 19 '13 at 0:29
  • 1
    $\begingroup$ And it is not hard to see that $3$ must divide $n$, so it can't ever be prime unless $n=3$. $\endgroup$ – Ian Mateus Dec 19 '13 at 0:31
  • 1
    $\begingroup$ Counterexample: $11$ and $35$ are coprime, but $11^{35}\equiv16\pmod{35}$ $\endgroup$ – Ian Mateus Dec 19 '13 at 0:40
  • $\begingroup$ @Tim, Ian: thank you both, I forgot that $n$ must be prime, although it's obvious in retrospect -- for general $n$ one needs to use $\phi(n)$ to satisfy the equation at every prime dividing $n$. Perhaps there's some way to leverage that here although I do not see it yet. $\endgroup$ – Marek Dec 19 '13 at 0:44
  • $\begingroup$ That is exactly what makes the problem hard... $\endgroup$ – fretty Dec 28 '13 at 10:43
0
$\begingroup$

This is not an answer.

So for far we know the following facts:

  1. The only $n\le 3\cdot 10^6$, for which this divisibility holds is $n=3$. (Tested numerically.)

  2. Clearly 3 and 5 do not divide $3^n+5^n$, and it is not hard to show that 7 and 11 also do not divide $3^n+5^n$.

  3. Hence if $n^2-1$ divides $3^n+5^n$, then 3,5,7,11 do not divide $n^2-1$. In particular, if if $n^2-1$ divides $3^n+5^n$, then 3 divides $n$.

$\endgroup$
  • $\begingroup$ @IanMateus: Thnx. Corrected. $\endgroup$ – Yiorgos S. Smyrlis Dec 22 '13 at 23:10
  • $\begingroup$ Could you please show more explicitly that $7$ and $11$ don't divide $3^n+5^n$? Thanks. $\endgroup$ – Ian Mateus Dec 27 '13 at 0:30
  • $\begingroup$ You have $5/3\equiv 4\pmod{7}$, and the order of $4\pmod{7}$ is $3$, so $4^k\not\equiv -1\pmod{7}$. In the same way $5/3\equiv 9\pmod{11}$ and the order of $-2\pmod{11}$is $5$, so $9^k\not\equiv -1\pmod{11}$. $\endgroup$ – Jack D'Aurizio Dec 27 '13 at 1:19
0
$\begingroup$

This seemed like a good starting point to examine the GMP C library in a little more detail, so I decided to write a quick program to print out numbers that fit this problem description. I'm not sure how much of an "answer" this is, but I thought the program might interest relevant parties.

Code below, link to a github gist here.

// This program is a quick brute force test of the question described at
// http://math.stackexchange.com/questions/612346/find-all-positive-integers-n-s-t-3n-5n-is-divisible-by-n2-1

// Copyright (C) 2014 Victor Robertson

// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

size_t gLower = 1;
size_t gUpper = (0 - 1); // force underflow = size_t max
size_t i;

void sig_handler(int signo)
{
    printf("tested %zu to %zu\n", gLower, i - 1);
    exit(0);
}

int main(int argc, char* argv[]) {

    // all n s.t. 3^n+5^n is divisible by n^2−1

    if (signal(SIGINT, sig_handler) == SIG_ERR) {
        return 1;
    }

    // set args if provided
    if (argc > 1) {
        gLower = atol(argv[1]);
        if (argc > 2) {
            gUpper = atol(argv[2]);
        }
    }

    i = gLower;

    mpz_t i_sqr, three_n, five_n, res;

    mpz_init(i_sqr);
    mpz_init(three_n);
    mpz_init(five_n);
    mpz_init(res);

    // start by calculating 3^n and 5^n where n is the first number to test
    mpz_ui_pow_ui(three_n, 3, i);
    mpz_ui_pow_ui(five_n, 5, i);

    // 3 is a known solution, might as well skip straight to 5
    if (gLower < 5) {
        printf("3\n");
        gLower = 5;
    }

    // adjust the lower bound to exclude odds
    if (gLower % 2 == 0) {
        gLower -= 1;
    }

    for(i = gLower; i < gUpper; i += 2) {
        // I think this can be accomplished in a better, possibly more efficient means though I'm not positive.
        mpz_ui_pow_ui(i_sqr, i, 2);
        mpz_sub_ui(i_sqr, i_sqr, 1);

        mpz_add(res, three_n, five_n);

        if (mpz_divisible_p(res, i_sqr)) {
            printf("%zu\n",i);
        }

        // multiple the current 3^n and 5^n by 3 and 5 respectively to acquire 3^(n+1) and 5^(n+1)
        mpz_mul_ui(three_n, three_n, 3);
        mpz_mul_ui(five_n, five_n, 5);
    }

    printf("Done!\n");

    mpz_clear(i_sqr);
    mpz_clear(three_n);
    mpz_clear(five_n);
    mpz_clear(res);
}
$\endgroup$
0
$\begingroup$

Since $n$ is odd, we have $(3^n+5^n)\mid (3^{n^2}+5^{n^2})$ and thus $(n^2-1)\mid (3^{n^2}+5^{n^2})$. In other words, both $n$ and $n^2$ must belong to the set $$S=\{ m\in\mathbb{N} : (m-1)\mid (3^m+5^m)\},$$ which is represented by the sequence http://oeis.org/A234535 in the OEIS.

It is therefore interesting to consider a (possibly simpler) question of finding all squares in $S$.

$\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.