# How many numbers?

How many numbers from 7, 13, 14, 21, 26, 39 and 91 divide $$(69^{12} − 38^{12})$$?

I am able to get the answer by calculating it.

But is there is any shorter way by which i can solve this?

-
I think that the point of the exercise was to show that you know how to factor $$x^n-y^n\text{ where n is any positive integer greater than }1$$ and $$x^n+y^n\text{ where n is any positive odd integer greater than 1}$$ – John Joy Oct 26 '14 at 12:33

You can calculate the expression in question modulo 7, 13, etc. For example, $69^{12}-38^{12} \mod 7 = (-1)^{12}-3^{12} \mod 7 = 1-2^{6} \mod 7 = 0$.

Another way is to note that $x^{12}-y^{12} = (x^6)^2-(y^6)^2 = (x^6-y^6)(x^6+y^6) = (x^3-y^3)(x^3+y^3)(x^6+y^6) = (x-y)(x^2+xy+y^2)(x^3+y^3)(x^6+y^6)$, and $69^2+69\times38+38^2 = 4761+2622+1444=8827=7\times13\times97$.

Also note that $14=2\times7$, $21=3\times7$, $26=2\times13$, $39=3\times13$ and $91=7\times13$. Yet $69^{12}-38^{12} = 3^{12}\times23^{12}-2^{12}\times19^{12}$ obviously does not divides neither $2$ nor $3$, so you have to check only divisibility by $7$ and $13$ (and conclude the divisibility by $91$ from that).

-

$$x^{12}-y^{12} = (x-y) (x+y) (x^2+y^2) (x^2-x y+y^2) (x^2+x y+y^2) (x^4-x^2 y^2+y^4)\\ x = 69, y=38$$ \begin{align*} 69^{12}-38^{12} &= (31)(107)(6205)(3583)(8827)(17877373)\\ &= (31)(107)(5 . 17 . 73)(3583)(7 . 13 . 97)(1657 . 10789)\\ &= 5 . 7 . 13 . 17 . 31 . 73 . 97 . 107 . 1657 . 3583 . 10789\\ \end{align*}

Complete factorization of $69^{12}-38^{12}$ is therefore

$$5 . 7 . 13 . 17 . 31 . 73 . 97 . 107 . 1657 . 3583 . 10789$$

And since there is no $2$ or $3$ there, only $7$ and $13$ divide $\bf{and}$ $\bf{ not}$ $14,21,26,39$ .

Also since $91 = 13 . 7, \hspace{4pt}$ the only numbers in your list that divides $69^{12}-38^{12}$ are $\{7,13,91\}$

-

First things first. You have an odd number minus an even number, so your difference will be odd. You can immediately eliminate 14 and 26.

As for the rest, you can use Fermat's Little Theorem. For any prime $p$, if $\gcd(a,p)=1$, then $a^{p-1}\equiv1\pmod p$ (It will be $0$ of course if a is divisible by $p$). This problem deals with the prime factors 3,7, and 13. In all of these cases, $p-1|12$.

Let's try $3$ as an example. $3$ divides $69$, but not $38$. We have

$69^{12}-38^{12}\equiv0-(38^2)^6\equiv0-1^6\equiv-1\pmod3$

So this number is not divisible by $3$, so you can eliminate $21$ and $39$ as well.

-

This is in principle the same as Mike's answer, but take properties of the given numbers more in account. If I have a list of parameters for repeatedly putting into the same problem then I automatically try to find regularities/systematics in the parameters before I do them one by one. (Here the list is so short, that possibly one would go one-by-one anyway, but the pattern for the simplification is quite obvious).

The idea to simplify the job is that of full prime-factorization of the parameters-list because we have a "divisibility"-problem. We see, that  7, 13, 14, 21, 26, 39 and 91  is in fact  7,2*7,3*7, and 13, 2*13,3*13,7*13  so we need only look at the factors  2,3,7 and 13  and thus reduce the list of parameters from 7 down to 4.
Next, we recall that due to Fermat $\small a^{p-1} \equiv 1 \pmod p$

1. (mod 13) we have $\small 4^{12} - (-1)^{12} \equiv 1 - 1 \equiv 0$ So 13 is a possible modulus

1. (mod 2) the second is divisible by 2 but not the first, so 2 and its multiples are impossible
2. (mod 3) the first is divisible by 3 but not the second, so 3 and its multiples are impossible
2. (mod 7) we have $\small (-1)^{12} - 3^{12} \equiv 1 - (3^6)^2 \equiv 1-1^2 \equiv 0$ so 7 is possible

1. we do not need to repeat to check 2 and 3.

So only 7,13 and 7*13 remain as possible moduli.

-

Here is a clear (hopefully to you) exposition of a solution using only elementary algebra. Using the identities $a^2-b^2=(a+b)(a-b)$ and $a^3\pm b^b=(a\pm b)(a^2\mp ab+b^2)$, we find \eqalign{ a^{12}-b^{12} &=\left(a^{6}+b^{6}\right)\left(a^{6}-b^{6}\right)\\ &=\left(a^{6}+b^{6}\right)\left(a^{3}+b^{3}\right)\left(a^{3}-b^{3}\right)\\ &=\left(a^{6}+b^{6}\right) \left(a+b\right)\left(a^2-ab+b^2\right) \left(a-b\right)\left(a^2+ab+b^2\right)\\ &= \left(a+b\right) \left(a-b\right) \left(a^2-ab+b^2\right) \left(a^2+ab+b^2\right) \left(a^{6}+b^{6}\right) \\ &= \left(a+b\right) \left(a-b\right) \left(a^2-ab+b^2\right) \left(a^2+ab+b^2\right) \left(a^2+b^2\right) \left(a^4-a^2b^2+b^4\right) \\ } which helps considerably in factoring this number: \eqalign{ 69^{12}-38^{12} &=& \left(69+38\right) \left(69-38\right)\\&& \left(69^2-69\cdot38+38^2\right) \left(69^2+69\cdot38+38^2\right)\\&& \left(69^2+38^2\right) \left(69^4-69^238^2+38^4\right)\\ &=& 107\cdot31\cdot3583\cdot8827\cdot6205\cdot17877373 } Next, notice that the divisors we wish to check are related: \eqalign{ 7&\text{is prime}\\ 13&\text{is prime}\\ 14&=2\cdot7\\ 21&=3\cdot7\\ 26&=2\cdot13\\ 39&=3\cdot13\\ 91&=7\cdot13 } Thus we need only consider the primes $2,3,7$ and $13$, and then use logic to answer whether the various divisors above, which are products of one or two of these primes, divide the result evenly. By trial division, we calculate the remainders in each row upon dividing each term (in the column header) by each prime (in the row header): $$\matrix{ &~& 107&31&3583&8827&6205&17877373\\ 2&~& 1 & 1 & 1 & 1 & 1 & 1 \\ 3&~& 2 & 1 & 1 & 1 & 1 & 1 \\ 7&~& 2 & 3 & 6 & 0 & 3 & 3 \\ 13&~& 3 & 5 & 8 & 0 & 4 & 7 }$$ From which we see that $7,13$ and their product $91$ are the only divisors from our list which evenly divide our quantity. The logic we need to use requires as axioms these properties of divisibility: \eqalign{ p|ab \quad\iff\quad& p|a \quad\text{or }\quad p|b \qquad\text{(or both)}\\ pq|c \quad\iff\quad& p|c \quad\text{and}\quad q|c } where $p,q$ are prime, $a,b,c$ are any integers, and $b|a$ meanst that $b$ divides $a$ (evenly), i.e. that $a=bc$ for some $c$.

For a more sophisticated method, we can use the concept of congruence or modular arithmetic and a theorem of Fermat (and possibly related ideas and theorems e.g. by Euler) from number theory relating powers of integers modulo a prime (or modulo a relatively prime number). These seem already adequately covered by other posts, so I'll stop here.

-

Hint $\ \ \$ If $\rm\ (ab,cd) = 1\$ then $\rm\ \phi(c),\phi(d)\ |\ n\ \ \Rightarrow\ \ c,d\ |\ a^n - b^n$

Proof $\$ Let $\rm\ n = \phi(c)\:\! k.\:$ Note $\rm\ (a,c)=1=(b,c)\:$ by $\rm\:(ab,cd)=1\:$, hence

Euler-Fermat $\rm\: \Rightarrow\ mod\ c\!:\ a^n-b^n=\!\:(a^{\phi(c)})^k - (b^{\phi(c)})^k\equiv 1^k-1^k\equiv 0$

-