I tried using factorization of $a^n-b^n$ for odd $n$ in an attempt to work through to a situation where the factors are such that they cannot have n as a factor. But I reached nowhere. Here's how I proceeded -


a-b=4 and can be ignored.

The latter term is essentially odd and not divisible by any odd number till $9$ (easy to prove without getting into calculations).

However, for some arbitrary odd number $x=p^k$ where $p \ge 11$ is prime, I cannot say whether the sum of two terms is divisible by $x$ or not when the two terms are individually not divisible by $x$.

  • $\begingroup$ Thanks. I used to use it a while ago and had forgotten. Edited now. :) $\endgroup$ Dec 16, 2015 at 15:34
  • $\begingroup$ @GottfriedHelms: Err that doesn't say anything about this question. An even number might have odd factors. $\endgroup$
    – user21820
    Dec 16, 2015 at 15:44

2 Answers 2


This is one of my favorite number theory problems because of the neat trick below :

Assume that $n$ is odd . Let $p$ be the smallest prime factor of $n$ (it's obviously odd and can't be $3$ or $7$)

From Fermat's little theorem :

$$7^{p-1}-3^{p-1} \equiv 1-1 \equiv 0 \pmod{p}$$

Also you know that :

$$p \mid n \mid 7^n-3^n$$

Now I'll use a standard lemma easily provable by induction :

Lemma If $a,b,n,m$ are positive integers and $(a,b)=1$ then : $$(a^n-b^n,a^m-b^m)=a^{(n,m)}-b^{(n,m)}$$

Use this lemma here so :

$$p \mid (7^{p-1}-3^{p-1},7^n-3^n)=7^{(n,p-1)}-3^{(n,p-1)}$$

Here comes the awesome part :

Because $p$ is the smallest prime factor of $n$ we must have $(p-1,n)=1$ . To see this assume that there is a prime $q$ such that $ q \mid n$ and $q\mid p-1$ this means that $q <p$ and $ q \mid n$ which contradicts the minimality of $p$

$(n,p-1)=1$ so we can simplify :

$$p \mid 4$$ which is a contradiction because $p$ is odd .

  • $\begingroup$ Insanely brilliant. I had no idea about Fermat's little theorem and also the Lemma which is a characteristic of factorization of any expression of the form $a^n-b^n$ .. I was attempting to solve using elementary Algebra.. which now makes me curious.. Is there a simpler way of proving it than the one you have given? $\endgroup$ Dec 16, 2015 at 16:02
  • $\begingroup$ I don't know of any other solution though I've seen this problem (or similar ones ) multiple times on AOPS . Maybe you can find something there . $\endgroup$
    – user252450
    Dec 16, 2015 at 16:06
  • 1
    $\begingroup$ The lemma needs the condition $\gcd(a,b)=1$, e.g. $\gcd\left(4^3-2^3,4^2-2^2\right)\neq 4^{\gcd(3,2)}-2^{\gcd(3,2)}$. The lemma with $\gcd(a,b)=1$ is easily provable with the method of my answer. $\endgroup$
    – user236182
    Dec 16, 2015 at 16:10
  • $\begingroup$ @ user236182 Thanks for the correction .I'll edit it . $\endgroup$
    – user252450
    Dec 16, 2015 at 16:13

If $n\mid 7^n-3^n$ and $n>1$, then let $p$ be the least prime divisor of $n$.

Clearly $\gcd(21,p)=1$, so $\left(7\cdot 3^{-1}\right)^n\equiv 1\pmod{p}$, i.e. $\text{ord}_p\left(7\cdot 3^{-1}\right)\mid n$.

By Fermat's Little theorem $\text{ord}_p\left(7\cdot 3^{-1}\right)\mid p-1$. Therefore $\text{ord}_p\left(7\cdot 3^{-1}\right)\mid \gcd(n,p-1)=1$, so $7\cdot 3^{-1}\equiv 1\pmod{p}$, so $7\equiv 3\pmod{p}$, so $p\mid 7-3=4$, so $p=2$.

  • $\begingroup$ I am not familiar with the mathematical notations you have used but I can sense that your answer and ComplexPhi's answers are essentially equivalent.. Is there an alternative (read: easier) way of proving the result? Thanks. $\endgroup$ Dec 16, 2015 at 16:04

You must log in to answer this question.

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