Prove $13|19^n-6^n$ by congruences

Question

I am trying to prove $13|19^n-6^n$. With induction its not so bad but by congruences its quite difficult to know how to get started.

Any hints?

Answer 1

HINT: Just use the congruence $19\equiv 6\pmod{13}$.

Answer 2

Modular Arithmetic is an extremely useful way of thinking about numbers. It can be used to calculate the last three digits of $2011^{2011}$ by hand. The day of the week, the time of the day, and the flipping of a light switch are all based upon modular arithmetic. The day of the week is in $\mod 7$ (cycles in a period of $7$), the time of the day is in $\mod 24$, and a light switch is either on or off; $\mod 2$.

Two integers are congruent modulo $n$ if their difference is a multiple of $n$. We write this as $$a \equiv b \pmod{n}$$ For example, $36 \equiv 71 \pmod{7}$, because $71 - 36 = 35$, and $\dfrac{35}{7} = 5$. We can alternatively write this as $a-b = qn$, for an integer $q$, or $a = b + qn$ (by adding $b$ to both sides). Notice that for any integers $x$ and $y$, if $x \equiv y \pmod{n}$, $x$ and $y$ leave the same remainder when divided by $n$. This is sometimes used as another definition for modular arithmetic. Since modular arithmetic is only defined for integers, let all variables be integers unless otherwise specified.

$\textbf{Addition}$

$\textbf{Theorem 1:}$ If $a \equiv b \pmod{n}$, then $a+c \equiv b+c \pmod{n}$.

If $a \equiv b \pmod{n}$, we know that $a-b = qn$ for some integer $q$. This means $(a+c) - (b+c) = a-b = qn$, so $a+c \equiv b+c \pmod{n}$. $\blacksquare$

If we know that $123$ leaves a remainder of $2$ when divided by $11$, and want the remainder when $127$ is divided by $11$, we can simply use Theorem 1: $123 \equiv 2 \pmod{11} \implies 123 + 4 \equiv 2 + 4 \pmod{11}$, so $127 \equiv 6 \pmod{11}$. A similar proof can be used to prove a stronger theorem:

$\textbf{Theorem 2:}$ If $a \equiv b \pmod{n}$, and $c \equiv d \pmod{n}$, then $a+c \equiv b+d \pmod{n}$.

We know that $a-b = qn$ for some integer $q$ and $c-d = rn$ for some integer $r$. Adding the equations gives $(a+c) - (b+d) = qn + rn = (q+r)n$. This means that the difference of $a+c$ and $b+d$ is a multiple of $n$, so $a+c \equiv b+d \pmod{n}$. $\blacksquare$

Theorem 2 can be generalized even further:

$\textbf{Theorem 3:}$ If $a_1 \equiv b_1 \pmod{n}$, $a_2 \equiv b_2 \pmod{n}$, $\cdots , \ a_k \equiv b_k \pmod{n}$ then $a_1 + a_2 + \cdots + a_k \equiv b_1 + b_2 + \cdots + b_k \pmod{n}$.

By the definition of modulos, we get $a_1 - b_1 = q_1 n$, $a_2 - b_2 = q_2 n$, $\cdots , \ a_k - b_k = q_k n$. Adding these, we get $(a_1 + a_2 + \cdots + a_k) - (b_1 + b_2 + \cdots + b_k) = (q_1 + q_2 + \cdots + q_k)n$, so $a_1 + a_2 + \cdots + a_k \equiv b_1 + b_2 + \cdots + b_k \pmod{n}$. $\blacksquare$

Similar theorems hold for muliplication as well, but the proofs are different.

$\textbf{Theorem 4:}$ If $a \equiv b \pmod{n}$, then $ac \equiv bc \pmod{n}$.

If $a \equiv b \pmod{n}$, we know that $a-b = qn$ for some integer $q$. This means $ac-bc = qcn$, so $ac \equiv bc \pmod{n}$. $\blacksquare$

There is also another proof of this:

We know that $$\underbrace{a \equiv b \pmod{n}, \ a \equiv b \pmod{n}, \cdots , \ a \equiv b \pmod{n}}_{\text{c statements}}$$ From Theorem 3, we get $$\underbrace{a+a+a+a+\cdots + a}_{\text{c "a"s}} \equiv \underbrace{b+b+b+b+\cdots + b}_{\text{c "b"s}}$$ or $ac \equiv bc \pmod{n}$. $\blacksquare$

$ \textbf{Theorem 5:}$ If $a \equiv b \pmod{n}$, and $c \equiv d \pmod{n}$, then $ac \equiv bd \pmod{n}$.

We repeatedly use Theorem 4: Since $a \equiv b$, $ac \equiv bc$, and since $c \equiv d$, $bc \equiv bd$. Therefore, $ac \equiv bc \equiv bd$, or $ac \equiv bd \pmod{n}$. $\blacksquare$

$\textbf{Theorem 6:}$ If $a_1 \equiv b_1 \pmod{n}$, $a_2 \equiv b_2 \pmod{n}$, $\cdots , \ a_k \equiv b_k \pmod{n}$ then $a_1 a_2 \cdots a_k \equiv b_1 b_2 \cdots b_k \pmod{n}$.

We repeatedly use Theorem 5: Because $a_1 \equiv b_1 \pmod{n}$, $a_2 \equiv b_2 \pmod{n}$, we get $a_1a_2 \equiv b_1b_2 \pmod{n}$. We also know $a_3 \equiv b_3 \pmod{n}$, so $a_1a_2a_3 \equiv b_1b_2b_3 \pmod{n}$. Also, $a_4 \equiv b_4 \pmod{n}$, so $a_1a_2a_3a_4 \equiv b_1b_2b_3b_4 \pmod{n}$. Continuing to do this will give $a_1 a_2 \cdots a_k \equiv b_1 b_2 \cdots b_k \pmod{n}$. $\blacksquare$

Note that a corollary of Theorem 6, when $a_1 = a_2 = \cdots = a_k$ and $a_1 = a_2 = \cdots = a_k$, is that

$\textbf{Theorem 7:} $ If $a \equiv b \pmod{n}$, then $a^k \equiv b^k \pmod{n}$.

$\textbf{Main Proof:}$ Using this corollary, we have $19^k \equiv 6^k \pmod{13}$, because $19 \equiv 6 \pmod{13}$. By definition, this means that $$13 | (19^k - 6^k)$$ as desired. $\blacksquare$

Answer 3

Hint: $19 \equiv 6 \mod 13$, so ...

Answer 4

Since $\displaystyle(x+y)^n = \sum_{k=0}^n \binom{n}{k}x^ky^{n-k}$, we have

$$19^n-6^n = (13+6)^n-6^n = \sum_{k=0}^n\binom{n}{k}13^k6^{n-k}-6^n=\sum_{k=1}^n\binom{n}{k}13^k6^{n-k}$$

Now the conclusion follows.

Answer 5

Because $x^n - y^n$ is divisible by $x-y$ as

$$x^n - y^n = (x-y)\sum_{i=0}^{n-1}x^iy^{n-1-i}$$

Substitute $x=19$ and $y = 6$.

---

$$\begin{align*} x^n-y^n =& x^n\left[1-\left(\frac yx\right)^n\right]\\ =& x^n \left[1+\left(\frac yx\right)+\left(\frac yx\right)^2+\cdots+\left(\frac yx\right)^{n-1}\right]\left[1-\left(\frac yx\right)\right]\\ =& \left(x^{n-1}y^0 + x^{n-2}y + x^{n-3}y^2 + \cdots + x^0y^{n-1}\right) (x-y) \end{align*}$$