calculate with large exponents

Question

Can somone explain me, how I can check if an number is an divisor of a sum with large exponents? Something like this:

Is $5$ a divisor of $3^{2012} - 4^{2011}$?

And how can I calculate something like that:

$39x \bmod 680 = 1$.

Thanks for your help

For some basic information about writing math at this site see e.g. here, here, here and here. — Julian Kuelshammer, Nov 11 '12 at 23:31

amWhy · Accepted Answer · 2012-11-12T14:46:47.317

3

For your second question, solving $$39x \bmod 680 = 1\tag{1}$$

is equivalent to solving the following congruence equation, $\bmod(680)$:

$$39x \equiv 1 \pmod{680}.\tag{2}$$

There is more than one solution: there are infinitely many solutions for $x$. Every integer $x$ which satisfies the following equation is a solution: $$39x = 680k + 1$$

Experiment with particular values for $k$ and see what values of $x$ you arrive at. Then try to define the set of all solutions.

ADDED: Solving $(2)$ gives us

$$x \equiv 279 \pmod{680}.\tag{3}$$

Then assuming you are looking for all integer solutions for $x$ we have, as solutions, all $x$ satisfying

$$x = 680k + 279\quad k\in \mathbb{Z}.\tag{4}$$

Note that when $k=0$, $x = 279$, which is the least positive solution solving your equation. So the set of all integer solutions satisfying $(1)$is given by $$\{x\mid x =279 \pm 680k, k\in \mathbb{Z}\}.$$

Please, in the future, if you have more than one sufficiently unrelated questions, post them separately.

edited Nov 12 '12 at 14:46

answered Nov 12 '12 at 00:11

amWhy

209,954

x=680k+279: How do I get the 279 ? – Tim Nov 12 '12 at 09:31
1

@Tim: one way to get the 279 is just to try - a spreadsheet makes this very quick-put 1 through 680 in column A, then in B1 put =mod(A1*39,680) and copy down. For larger numbers, look at the Extended Euclidean algorithm – Ross Millikan Nov 12 '12 at 14:52
@RossMillikan - +1 nice suggestion; spreadsheets come in handy for such tasks, and also for getting insight into problems. Also, nice link. – amWhy Nov 12 '12 at 15:19
I still don't get, how you got the 279 ? With a spreadsheet, but how do you do it with one? – Nov 12 '12 at 20:43
$\ddot\smile~~~~~~$ – Mikasa Aug 24 '13 at 12:02

score 2 · Answer 2 · answered Nov 11 '12 at 23:33

You can look at $3,3^2,3^3,\dots$, reducing each modulo $5$, until you see (and can prove) a pattern; then do the same with $4,4^2,4^3,\dots$.

Your other question is different --- you should make it a separate question (or, better, search the site, because that kind of linear congruence has been discussed here many times).

calculate with large exponents

2 Answers2