A Theorem on Arithmetic Progression and Divisibility

-

A Theorem on Arithmetic Progression and Divisibility

In this post, we briefly discuss a particular theorem concerning the divisibility of a sequence of terms in arithmetic progression. Before that, let's take a quick review of an arithmetic progression. 

Arithmetic Progression:

A sequence of numbers that have the same common difference between consecutive terms is said to be an arithmetic progression. For example, 

` 1, 5, 9, 15, 19, ... ` 

is a sequence of numbers that have a common difference of `4`. Mark that is not the absolute difference but rather algebraic difference. Thus the above is said to be an increasing AP with common difference `4`. 
The common difference is taken algebraically as (any term) - (the previous term). More examples:

` \frac{1}{2} , 1, \frac{3}{2}, 2, \frac{5}{2}, ... `

` \sqrt{10}, \sqrt{10} - \sqrt{2}, \sqrt{10} - 2\sqrt{2}, ... `

See also that any series of consecutive terms taken from an arithmetic progression also form an arithmetic progression.

General Notation:

Any arithmetic progression has the general form, 

`a, a + d, a + 2d, ...., a + (n-1)d`

where, `a \to ` first term
            `d \to ` common difference
            `n \to` term index

Thus the `n`th term is of the form `a_{n} = a + (n-1)d`.

An Interesting Property:

Here, we see an interesting property that can be particularly helpful in Number Theory. The theorem is as follows:

Theorem- Suppose an arithmetic progression with common difference `d`, in its infinite spread[1], contains at least one term divisible by `n`, then for any sequence of `n` consecutive terms taken from the arithmetic progression, the following hold:
  1. If `n | d`, then all the terms in the sequence are divisible by `n`. 
  2. If `n ∤ d`, then there exists at least one term in the sequence that is divisible by `n`.
Proof: First let's imagine the arithmetic progression. Since we know at least one term divisible by `n`, let's consider this term to be our first term. Of course this is purely arbitrary, and we could have taken any term and it would make no difference. But for convenience we take it as the first term. Since it's divisible by `n`, let's write it as `a_{0} = An` where `A` is some integer. 

Then the arithmetic spreads towards both left and right of `An` with common difference `-d` and `d` respectively,


`..., An - 2d, An - d, An, An + d, An + 2d, ... `


Suppose the chosen sequence of `n` terms be given by, 


` b_{1}, b_{2}, b_{3}, . . . , b_{n-1}, b_{n} `


Since any of these terms is part of the arithmetic progression they can be related to the first term in the form of  `An + Kd` where `K` is some integer. So if in the sequence , `b_{1}, ..., b_{n}` each term is obtained by adding `d` to the previous term, then we can write the sequence as, 


`An + Kd, An + (K+1)d, An + (K+2)d, ..., An + (K + n-1), An + (K+ n)d `


Indeed if `n | d`, then all these terms are divisible by `n`. So the first part is trivial. What remains for us is to show that at least one of the numbers `Kd, (K+1)d, . . ., (K+n)d` is divisible by `n`even if `n ∤ d` . 

If `n | K`, the job is done. If not, then it will leave some remainder. If the remainder is 1, then `n` will completely divide `K + n - 1 `. If the remainder is `2`, `n` will completely divide `K + n - 2`, and continuing if the remainder is `n-1`, then `n` will completely divide `K+1`. 

Having exhausted all possible remainders we are sure that at least one the terms is divisible by `n`. The proof is thus complete.











___________________________________

NOTES:

[1] By infinite spread I mean that sequence of arithmetic progression can be, by following the pattern, be extended along both the left and right sides upto a indefinitely large number of terms. When such a thing is done, what we get is an infinitely spread sequence. Since this sequence has an indefinitely large number of terms towards both the sides, there is no special first term. Therefore we are free to choose the first term ourselves. But once we select the first term (the term with index `1`), the other indexes are also defined. Also see that, the formula `a_{n} = a_{0} + (n-1)d ` holds for even `0` and negative indexes.
















Comments

Post a Comment

Popular posts from this blog

Animating AC Phasors

-
Image
(Refresh the browser once more for the equations to load properly) Animating AC Phasors In this post, we try to get an intuitive feeling about special quantities called phasors, used to represent current and voltage in AC circuits. We will see the theory at work, learning about complex numbers, sinors, and how these are used to represent voltage and current. At the end, we'll be able to input our custom values in the animation! Sinusoids: Any quantity that varies in the form of a sine or a cosine function is called a sinusoid. When a sinusoidally time-varying voltage is applied across an electrical component we get a corresponding sinusoidally time-varying current which we call an Alternating Current (AC). The voltage applied is called the alternating voltage. In the general form if ` v(t) = V_{0} sin(ωt) `, then the current is in the form ` i(t) = I_{0} sin(ωt + φ) `, where ` φ ` is called the phase difference, created by the properties of the ele...
Read more

Transient States in RL Circuits: The Journey to Steady-State

-
Image
(Refresh the browser once more for the equations to load properly) Transient States in RL Circuits: The Journey to Steady-State  In this article, we attempt to obtain the complete solution of an RL circuit, including the transient state. We first consider the case of a DC voltage, where the current gradually builds up and after that, we take up the special case of AC Voltage which is often skipped in elementary courses. Fig: Growth of current in cases of DC and AC voltages DC Voltage: A DC Voltage refers to a steady voltage that does not vary with time. The below diagram shows a simple DC circuit involving a resistor `R` and an inductor `L`. A cell acts as the source of a DC emf E. Fig: A simple RL circuit with DC emf From Kirchhoff's Voltage Law, we know that the magnitude of the net Voltage drop across a loop is equal to the magnitude of the net emf in that loop. The voltage drop due to the resistor is `iR` and due to the inductor is `L \frac{di}{dt}`. Thus we m...
Read more

Derivative of Products & Quotients

-
Image
Derivative of Product and Quotient The derivatives are widely used throughout Mathematics and the Sciences, and the Identities simplifying computations are invaluable tools. In this post, our intent is to derive the multiplication and division identities of derivatives using the very first principles. Derivative Suppose there be a continuous real function ` y = f(x) ` defined over an open interval `(a, b) \subseteq \mathbb{R}`. Then the derivative of the function `f(x)` at some point `c \in (a, b)` represented by, `f'(c) or \frac{d}{dx}f(x)` at `x = c` gives the rate of change of the function at the point `c` with respect to the independent variable. This idea however is still vague and we need a precise mathematical definition.   Right-hand & Left-hand Rate: In the neighbour of `c`, let us define an interval `I = [c - h, c + h]` for some ` h > 0`. Then we may define the right-hand average rate of change of the function in the interval as,  `\frac{f(c+h) - f(c)...
Read more