Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thanks in advance.

share|improve this question
    
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 at 12:33

6 Answers 6

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).

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.