5
$\begingroup$

I am asked to prove by induction that $7\times11^{2n+1}-3^{4n-1}$ is divisible by $10$.

I wonder whether there is a more direct method, for example factorizing by $10$. If an expression is divisible by $10$, does this mean that I can factorize it by $10$?

Thanks in advance

$\endgroup$
6
  • 3
    $\begingroup$ Just think about the last digit. $\endgroup$ Sep 19, 2020 at 17:04
  • 2
    $\begingroup$ With any statement about the set $\Bbb N$ (especially, when the claim doesn't hold for a larger set), a proof by induction is arguably the most direct one. This is somewhat by definition of $\Bbb N$ $\endgroup$ Sep 19, 2020 at 17:05
  • 2
    $\begingroup$ Are you familiar with congruences such as $\,11^2\equiv 3^4\pmod{10}\,?\ \ $ $\endgroup$ Sep 19, 2020 at 18:37
  • $\begingroup$ I take it you mean for $n\ge 1$. The persistence of divisibility can be shown in various ways. The numbers $k_n=Aa^n+Bb^n$ satisfy the recurrence $k_{n+1}=(a+b)k_n-abk_{n-1}$ (you can easily verify this by substitution) so (in appropriate cases) once you show that two successive elements are divisible by $d$ then they all are. These problems are quite often used as examples for induction. $\endgroup$ Sep 19, 2020 at 19:39
  • $\begingroup$ Thank you all so much for those answers that will help me more deeply understand this kind of problems. I just still hesitate on this : if an expression in N is divisible by 10, does this mean that I can factorize it by 10 ? $\endgroup$
    – Romain
    Sep 19, 2020 at 22:06

9 Answers 9

2
$\begingroup$

A direct and intuitive way. Every integer power of $11$ has $1$ as last digit, so every number of the form $7 \cdot 11^{2n+1}$ ends with the digit $7$.

The last digits of the integer powers of $3$ follows the four-step cycle $(3,9,7,1)$, so that every number of the form $3^{4n-1}$ has $7$ as last digit.

Therefore, subtracting this second number from the first one we get a number ending with the digit $0$. This implies that this last number is divisible by $10$.

$\endgroup$
2
$\begingroup$

Below are four proofs using various methods.


You seem to seek a direct proof showing a factor of $10$ so let's do that first.

$$\begin{align} x &\,=\ \ \ \ \, 7\cdot 11^{\large 2n+1}\ -\ 3^{\large 4n-1}\\[.2em] \Rightarrow\ \ 3x &\,=\ \ \, 21\cdot 11\cdot 121^n - 81^n\\[.2em] &\,=\, (21\cdot11\!-\!1)121^n+ \color{#0a0}{121^n-81^n}\\[.2em] &\,=\, \color{#c00}{10}\,(23\cdot 121^n + \color{#c00}4(121^{n-1} + \cdots + 81^{n-1}))\ \end{align}\qquad$$

where we used the Factor Theorem to deduce $\,\color{#c00}{10\cdot 4} = 121\!-\!81\,$ divides $\,\color{#0a0}{121^n-81^n}.\,$ Thus $\,10\mid 3x\Rightarrow 10\mid x\,$ by Euclid (or directly $\,10\mid 7(3x)\!-\!20x = x,\,$ or cancel $3$ from $121$'s and $81$'s).


It's much easier by modular arithmetic (congruences)

$$\begin{align}\bmod 10\!:\ \ 3x &\equiv 21\cdot 11^{\large 2n+1} - 81^{\large n}\\ \iff\ 3x &\equiv \ \ 1\ \cdot\ 1^{\large 2n+1}\ -\ 1^{\large n} \equiv\color{#0a0} 0\\ \iff\ \ \ x &\equiv\,3^{-1}\cdot\color{#0a0} 0\equiv 0 \end{align}\qquad$$

by basic congruence laws. We used the fact that scaling by an invertible (here $3$) yields an equivalent congrence (recall by Bezout that $3$ is invertible being coprime to the modulus $10)$


By induction: base case $\,n=1\,$ is $\!\bmod 10\!:\ 7\cdot 11^3\equiv 3^3\,$ (or $\,7\cdot 11\equiv 1/3\,$ for $\,n=0)\,$ which are both true, and the induction step follows conceptually by simply by multiplying the first two congruences below using $\rm\color{#0a0}{CPR} =$ Congruence Product Rule,

$$\begin{align}\bmod 10\!:\qquad\ \ \ \color{#c00}{11^{\large 2}}\ &\equiv\ \color{#c00}{3^{\large 4}}\\[.2em] {\rm times}\ \ \ \ \ \ \ 7\cdot 11^{\large 2n+1}&\equiv3^{\large 4n-1}\quad \ P(n)_{\phantom{|}}\\[.2em] \hline \Longrightarrow\ \ \ \ \ 7\cdot 11^{\large 2n+\color{#c00}3}&\equiv 3^{\large 4n+\color{#c00}3}\quad\ P(n\!+\!\color{#c00}1), \ \ \rm by \ \,\color{#0a0}{CPR}^{\phantom{|^|}}\end{align}\qquad $$

If congruences are unfamiliar we can preserve the arithmetical essence of this simple proof by using an analogous product rule for divisibility (DPR), as explained here.


Or as here use Binomial Theorem on $\,(1\!+\!10)^{2n+1}$ and $(-1\!+\!10)^{4n-1}$ (or $\,(1\!+\!80)^n\,$ in $3x)$


Remark $ $ All these methods do in fact use induction (on $n),\,$ but it may be hidden (encapsulated) in the proof of a theorem that is invoked, e.g. the Factor Theorem or Binomial theorem, or the Congruence Power Rule $\,a\equiv b\Rightarrow\, a^n\equiv b^n$.

$\endgroup$
4
  • $\begingroup$ Thank you all so much for those answers that will help me more deeply understand this kind of problems. I just still hesitate on this : if an expression in N is divisible by 10, does this mean that I can factorize it by 10 ? $\endgroup$
    – Romain
    Sep 19, 2020 at 22:11
  • $\begingroup$ @Romain $\,10\mid n,\,$ i.e. $10$ divides $n$ means by definition that $\, n = 10k\,$ for some integer $k,\,$ It is often quicker to prove that in ways that don't require explicitly calculating the integer cofactor $k = n/10$ that is witness to the divisibility, e.g. using modular arithmetic (congruences) as above. $\endgroup$ Sep 19, 2020 at 22:14
  • $\begingroup$ " if an expression in N is divisible by 10, does this mean that I can factorize it by 10 ?" Yes, but you might not always know how. $\endgroup$
    – fleablood
    Sep 20, 2020 at 1:02
  • 2
    $\begingroup$ Sadly there seems to be at least one user who consistently downvotes ansers that have multiples proofs. In the unlikely chance that this has anything to do with matehmatics then please leave a constructive comment so that any deficiency you perceive may have a chance to be addressed. $\endgroup$ Sep 20, 2020 at 19:30
1
$\begingroup$

we have $$7{(10+1)}^{2n+1}-3{(10-1)}^{2n-1}$$

indeed by binomial theorem it is equivalent to:

$$7(10k+1)-3(10m-1)=10+70k-30m$$

which is div by $10$

$\endgroup$
1
$\begingroup$

Using modular arithmetic: \begin{align}3(7\cdot 11^{2n+1}-3^{4n-1})&=21\cdot 11^{2n+1}-9^{2n}\\&\equiv 1\cdot (1)^{2n+1}-(-1)^{2n}\\&=0 \pmod {10}.\end{align}

$\endgroup$
0
$\begingroup$

We have $$3(3^3)=81 \equiv 1 \pmod{10}$$

$$3^{-1}\equiv 3^3 \equiv 7 \pmod{10}$$

\begin{align} 7(11^{2n+1})-3^{4n-1} &\equiv 7 (1^{2n+1}) - (3^4)^n3^{-1}\\ &\equiv 7(1)-(1)(7) \\ &\equiv 0 \pmod{10} \end{align}

$\endgroup$
0
$\begingroup$

Best method? Depends on what you know.

If you know modular arithmetic and Eulers Theorem then

$7\cdot 11^{2n+1} - 3^{4n-1}\equiv 7\cdot 1^{2n+1} - (3^{-1})\cdot 3^{4n}\equiv 7-(3^{-1})\pmod{10}$ and as $3\cdot 7 \equiv 1 \pmod {10}$ then $3^{-1}\equiv 7 \pmod {10}$ and $7-7\equiv 0\pmod {10}$ so $10|7\cdot 11^{2n+1} - 3^{4n-1}$.

But that assumes you are comfortable with many concepts

If you don't know any modular arithmetic:

$11^k = (10+1)^k = 10^k + k10^{k-1} + ...... + k\cdot 10 + 1 = 10 M + 1$.

And $3^{4n-1} = 3\times 3^{4n-2}= 3\times 9^{2n-1}$. And if $k=2n-1$ is odd the $9^k = (10-1)^k = 10^k - k10^{k-1} + ....... + k\cdot 10 - 1= 10N-1$.

So $7\cdot 11^{something} - 3^{1+2\times something\ odd} = 7(10M + 1)- 3(10N-1)= 70M -30N +10$.

$\endgroup$
3
  • $\begingroup$ You didn't invole Euler (maybe you meant to say Euclid for computing the inverse?) $\endgroup$ Sep 20, 2020 at 1:29
  • $\begingroup$ I meant Euler and I meant that $3^{4n} \equiv 1\pmod {10}$ so $3^{4n-1} \equiv 3^{-1}$. $\endgroup$
    – fleablood
    Sep 20, 2020 at 2:15
  • $\begingroup$ Ah, I didn't expect use of Euler in such a simple case since it is much easier by repeated squaring $\!\bmod 10\!:\ (3^2)^2\equiv (-1)^2\equiv 1,\,$ or even directly $\,(3^2)^2\equiv 9^2\equiv 81\equiv 1.\ \ $ $\endgroup$ Sep 20, 2020 at 2:24
0
$\begingroup$

Since

$\quad 11^k \equiv 1 \pmod{10} \quad \forall k \in \Bbb Z$

and

$\quad 3^{4n-1} \equiv {(3^2)}^{2n} \times 3^{-1} \equiv (-1)^{2n} \times 7 \equiv 7 \pmod{10}$

we can write

$\quad 7\times11^{2n+1}-3^{4n-1} \equiv 7 - 7 \equiv 0 \pmod{10}$


Elementary Number Theory:

The invertible elements in $\mathbb{Z}/{10}\mathbb{Z}$ are

$\quad [1], [3], [7] \text{ and } [9]$

allowing one to quickly determine that $3^{-1} \equiv 7 \pmod{10}$.

$\endgroup$
0
$\begingroup$

The OP is looking for a factorization argument and so we give a problem/hint that can be directly solved without elementary number theory using simple algebra; this is the step case of the induction proof.

Problem: Show that if $k \ge 1$ and

$\tag 1 \displaystyle 7\times11^{2k+1}-3^{4k-1} = 10q$

then

$\tag 2 \displaystyle 7\times11^{2(k+1)+1}-3^{4(k+1)-1} = 10 \times (11^2 q + 4 \times 3^{4k-1})$

$\endgroup$
0
$\begingroup$

Multiply $n=7\times11^{2n+1}-3^{4n-1}$ by $3$ to get $3n=21\times11^{2n+1}-81^{n}$, which is divisible by $10$

(ones digit is $0$, because it is the difference of two numbers whose ones digit is $1$).

Now if $3n$ is divisible by $10$, for an integer $n$, then $n$ is divisible by $10$. QED.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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