0
$\begingroup$

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

  • 0
    For some basic information about writing math at this site see e.g. [here](http://meta.math.stackexchange.com/questions/5020/), [here](http://meta.stackexchange.com/a/70559/155238), [here](http://meta.math.stackexchange.com/questions/1773/) and [here](http://math.stackexchange.com/editing-help#latex).2012-11-11

2 Answers 2

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.

  • 0
    x=680k+279: How do I get the 279 ?2012-11-12
  • 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](http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm)2012-11-12
  • 0
    @RossMillikan - +1 nice suggestion; spreadsheets come in handy for such tasks, and also for getting insight into problems. Also, nice link.2012-11-12
  • 0
    I still don't get, how you got the 279 ? With a spreadsheet, but how do you do it with one?2012-11-12
  • 0
    $\ddot\smile~~~~~~$2013-08-24
2

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