Mathematics and Such

Order of an Element Modulo m and Applications – Part I

Posted on November 6, 2011 by limsup

Background required : modular arithmetic

If you’ve any experience observing powers of numbers, you’d have noticed that the last digit runs in cycles: e.g. if you take the last digits of successive powers of 7, you get 7 → 9 → 3 → 1 → 7 → 9 → 3 → 1 → … . More generally, if you start with a positive integer m and take an a which is coprime to m then it’s not hard to see that the successive powers 1, a, a², a³, … modulo m must run in a cycle eventually. Why? Because since each of these powers is congruent to some c mod m, 0 ≤ c ≤ m-1, and there are only finitely many possibilities of c, eventually we have aⁱ ≡ a^j (mod m) for some 0 < i < j. And since (a, m) = 1, we can perform cancellation by aⁱ to obtain a^j-i ≡ 1 (mod m).

E.g. if we pick mod 11, and a = 2, the cycle is given by:

1 → 2 → 4 → 8 → 5 → 10 → 9 → 7 → 3 → 6 → 1

Or if we pick mod 35 and a = 3, we get:

1 → 3 → 9 → 27 → 11 → 33 → 29 → 17 → 16 → 13 → 4 → 12 → 1

Recall that Fermat’s Little Theorem gave us an upper bound for the length of the cycle when p is prime, since a^p-1 ≡ 1 (mod p) if a is not divisible by p. For the general case, we have Euler’s Theorem:

Theorem. Let m be a positive integer and (a, m) = 1. Then $a^{\phi(m)} \equiv 1 \pmod m$ , where φ(m) = Euler’s totient function = the number of i between 0 and m-1 inclusive such that i and m are coprime.

Proof. Let $b_1, b_2, \dots, b_{\phi(m)}$ be the distinct elements in [0, m-1] which are coprime to m. Consider the products $ab_1, ab_2, \dots, ab_{\phi(m)}$ . For each i = 1, 2, …, φ(m), we can pick c_i between 0 and m-1 such that $c_i \equiv ab_i \pmod m$ . Now all the c_i‘s are distinct: indeed if c_i = c_j then $ab_i \equiv ab_j \pmod m$ and since a is coprime to m, we get $b_i \equiv b_j \pmod m$ , which is a contradiction. Hence, the c_i‘s are just a permutation of the b_i‘s. If we take the product of them all, we get:

$\displaystyle\prod_{i=1}^{\phi(m)} b_i = \prod_{i=1}^{\phi(m)} c_i \equiv \prod_{i=1}^{\phi(m)} (ab_i) = a^{\phi(m)} \prod_{i=1}^{\phi(m)} b_i \pmod m.$

Since each b_i is coprime to m, we can apply cancellation to obtain $a^{\phi(m)} \equiv 1 \pmod m$ . ♦

Thus, Euler’s theorem gives us an upper bound on the length of a cycle when we take the successive powers of an element modulo m.

Let a be an integer coprime to m – we write ord_m(a) for the smallest positive integer d for which $a^d \equiv 1 \pmod m$ . In other words, ord_m(a) is the length of the cycle when we consider the successive powers of a modulo m. Hence, the above examples give us ord₁₁(2) = 10, ord₃₅(3) = 12. Note that we always have ord_m(1) = 1.

Caution. The notation ord_m(a) is sometimes used for another wholly different concept. When p is a prime, ord_p(a) is also used to denote the highest r for which p^r divides a. Thus, ord₅(500) = 3 for example. It’s thus safer to describe in words: let d be the multiplicative order of a modulo m …

The key property we shall make use of is as below.

Let d = ord_m(a). Suppose k is some positive integer such that $a^k \equiv 1 \pmod m$ . Then k must be a multiple of d.

From the cycle diagram this should be obvious, but let’s give a quick proof anyway.

Proof. Dividing k by d, we can write k = qd + r, where 0 ≤ r ≤ d-1. Then we get:

$1 \equiv a^k = a^{qd+r} = (a^d)^q\cdot a^r \equiv 1 \cdot a^r \pmod m$

and so $a^r \equiv 1 \pmod m$ . Since r < d and we assumed d to be the smallest positive integer satisfying $a^d \equiv 1 \pmod m$ , we must have r = 0, and so k is a multiple of d. ♦

Coming up next: applications in problem solving …

Posted in Notes | Tagged intermediate, notes, number theory | Leave a comment

Homework (29 Oct 2011)

Posted on November 4, 2011 by limsup

The homework for last week was a little harder than the prior one:

Let n be a positive integer, $n \equiv 23 \pmod {24}$ . Prove that the sum of the divisors of n is a multiple of 24.
Let N = 2¹⁰ × 3⁹ × 5⁸. Calculate:

the number of divisors of N;
the sum of all divisors of N;
the number of i modulo N which are coprime to N.

Let p be a prime number and a be an integer not divisible by p. Suppose d is the smallest positive integer for which a^d – 1 is divisible by p. Prove that d | (p-1).
Prove that there exist distinct positive integers x₁, x₂, …, x₂₀₁₁, such that both conditions hold:

$x_1^2 + x_2^2 + \dots + x_{2011}^2$ is a cube;
$x_1^3 + x_2^3 + \dots + x_{2011}^3$ is a square.

Find the remainder when $[(1 + \sqrt 2)^{2011}]$ is divided by 3, where [x] denotes the largest integer ≤ x. E.g. [3.5] = [3] = 3 and [-4.5] = [-5] = -5.

Posted in Homework | Tagged basic, homework, number theory | Leave a comment

Number Theory and Calculus/Analysis

Posted on November 1, 2011 by limsup

Background required: modular arithmetic, calculus.

Once in a while, I’ll post something which offers a glimpse into more advanced mathematics. Here’s one.

Example 1

For starters, we know from basic algebra that $(1-r)^{-1} = 1 + r + r^2 + \dots$ . Let’s see if there’s a corresponding result for modular arithmetic: letting r = 14 and taking modulo 7⁴, we get:

$-\frac 1 {13} = (1-14)^{-1} = 1 + 14 + 14^2 + 14^3 + ...$

where the remaining terms are chopped off since they’re divisible by 7⁴. Now, the right-hand-side simplifies to 2955 mod 2401 = 554, and indeed we have $-\frac 1 {13} \equiv 554 \pmod {7^4}$ since $13\times 554 \equiv -1 \pmod {7^4}$ . Hence, we have simplified the computation of inverse modulo a prime power by converting it to multiplication. Purists would no doubt complain that we shouldn’t substitute r = 14 since the infinite geometric series only holds for |r| < 1, but as you can see we still got the right answer. 🙂

Example 2

Next, we know from calculus that binomial expansion gives:

$(1 + x)^r = 1 + r x + \frac {r(r-1)} {2!} x^2 + \frac {r(r-1)(r-2)} {3!} x^3 + \dots$

which converges when |x| < 1 and r is any number (even irrational). Let’s see if we can’t apply this to modular arithmetic. Say, for example, we wish to find an x such that $x^2 \equiv 2 \pmod {7^4}$ , i.e. x is the square root of 2 modulo 2401 = 7⁴. Then the above binomial expansion gives us:

$2\sqrt 2 = \sqrt 8 = (1 + 7)^{\frac 1 2} = 1 + \frac 1 2 \cdot 7 + \frac {\frac 1 2 \cdot \left(-\frac 1 2\right)} 2 \cdot 7^2 + \frac {\frac 1 2 \cdot \left(-\frac 1 2\right) \cdot \left(-\frac 3 2\right)} 6 \cdot 7^3 + \dots$

Again, the remaining terms may be ignored since they’re all divisible by 7⁴. Since $2 \times 1201 \equiv 1 \pmod {7^4}$ , we write $\frac 1 2 \equiv 1201 \pmod {7^4}$ , we then obtain the following:

$\sqrt 8 \equiv 470 \pmod {7^4}.$

Dividing by 2, we thus get $\sqrt 2 \equiv 235 \pmod {7^4}$ . You can easily check that 235² is indeed congruent to 2 modulo 7⁴.

Example 3

Or another example would be the Newton-Raphson method: to find a zero of the function f(x), start with a point x₀, and iterate:

$x_{n+1} = x_n - \frac {f(x_n)} {f'(x_n)},$

where f’ is the derivative of x. Let’s see if we can apply this method to find the solution to, say:

$x^3 - x + 1 \equiv 0\pmod {7^4}.$

So f(x) = x³ – x + 1 and the recurrence is given by $x_{n+1} = x_n - \frac {x_n^3 - x_n + 1} {3x_n^2 - 1} = \frac {2x_n^3 -1}{3x_n^2 - 1}$ . Since we have to perform division modulo 7⁴, the answer is not so easily computable. Instead, we shall leave our answer as a rational fraction a/b, where a and b are integers.

First, note that x₀ = 2 satisfies $f(x) \equiv 0 \pmod 7$ so let’s start from there:

$x_0 = 2, \quad x_1 = \frac {15} {11}, \quad x_2 = \frac {5419} {6094}.$

This turns out to be the right answer! Indeed, $\frac 1 {6094} \equiv 1745 \pmod {7^4}$ , so $x_2 \equiv 1745 \times 5419 \equiv 1017 \pmod {7^4}$ and one easily checks that this is a valid solution to $x^3 - x + 1 \equiv 0 \pmod {7^4}$ .

Explanation

What’s going on here? We carried out a bunch of computations which seemed utterly nonsensical but which yielded the right answer. For a proper understanding of the underlying theory, one needs to study p-adic analysis (where the p here refers to a prime). Indeed, one can go on to define logarithm and exponentiation and most of the usual relations among them still hold. On the one hand, it is possible to be led astray by one’s intuition from the real case; on the other hand, convergence in the p-adic case is extremely fast! For instance, the Newton-Raphson process gave us the correct answer by the 2nd iteration.

The gist of the theory is as follows. Let p be a prime.

We define a new “absolute value” on the set Q of rational numbers. If r is a non-zero rational, then |r|_p is defined to be the unique p^m (m integer) such that p^mr is of the form a/b where a and b are both not divisible by p. E.g. if p = 5, then |250|₅ = 1/125, |17/198|₅ = 1 and |12/25|₅ = 25.
Recall that our good-old |x–y| determines how close x and y are on the number line. For |r–s|_p, closeness means r and s are congruent to each other modulo a huge power of p.
We have the triangular inequality $|r+s|_p \le |r|_p + |s|_p$ . In fact, we have the strong triangular inequality $|r+s|_p \le \max(|r|_p, |s|_p)$ . If you unwind the definition, it just means that if r and s are divisible by p^r, then so is r+s. The triangular inequality ensures that we can define a theory of analysis (or even calculus) on it.
One consequence of the strong triangular inequality is that convergence occurs very quickly, as we have already seen from the above examples. Compare this to the case of real numbers, where convergence can be slow, e. g. in $\frac 1 {1-x} = \sum_n x^n$ when x = 0.99.
E.g. in example 1, we get $|14|_7 = \frac 1 7 < 1$ which ensures convergence.

Feel free to try out more computations of the above type. To carry out multi-precision integer computation (> 12 digits), download Python.

Posted in Extra | Tagged advanced, analysis, calculus, extra, notes, number theory, p-adic | 2 Comments

Number Theory Notes (22 Oct 2011) – Part III

Posted on October 28, 2011 by limsup

Finally, we shall solve two more problems – the last problem is rather surprising since at first glance, it doesn’t appear to involve congruences.

Problem 4 : Prove that if n is a perfect square, then $n^2 \equiv 0, 1 \pmod 4$ .

Solution : this is rather simple: one could always write n = m² and consider all possibilities of m modulo 4. But it’s easier to just consider m mod 2:

If m = 2k is even, then m² = 4k² is a multiple of 4.
If m = 2k+1 is odd, then m² = 4k² + 4k + 1 is congruent to 1 mod 4. ♦

The next problem illustrates a common technique, called infinite descent.

Problem 5 : Prove that the only solution of $x^2 + 2y^2 = 5z^2$ in integers is x = y = z = 0.

Solution : first it is clear that if x = 0 or y = 0, then we must have x = y = z = 0. Hence we assume that x, y and z are all non-zero. Taken modulo 5, we have

$x^2 \equiv 0, 1, 4 \pmod 5, \quad 2y^2 \equiv 0, 2, 3 \pmod 5.$

Hence, the only possibility for $x^2 + 2y^2$ to be a multiple of 5 is $x^2 \equiv y^2 \equiv 0 \pmod 5$ . Thus x and y are both multiple of 5: write x = 5x’ and y = 5y’ which gives $25x'^2 + 50y'^2 = 5z^2$ , i. e. $5x'^2 + 10y'^2 = z^2$ . But this in turn means z is a multiple of 5: z = 5z’, so we are back to the original equation:

$x'^2 + 2y'^2 = 5z'^2.$

Since x, y and z are non-zero, so are x’, y’ and z’. But here the trouble begins: we can apply the same logic above and come to the conclusion that x’, y’ and z’ are also all multiples of 5, and so on, and so on. Thus, x, y and z are divisible by arbitrarily high powers of 5(!) which is clearly impossible if they are non-zero. ♦

Posted in Notes | Tagged basic, notes, number theory | Leave a comment

Number Theory Notes (22 Oct 2011) – Part II

Posted on October 28, 2011 by limsup

Now we will solve actual problems with the theory we’ve just learnt.

Problem 1 : Find all integers x such that x ÷ 5 has remainder 3, x ÷ 7 has remainder 6 and x ÷ 9 has remainder 2.

Solution : This can be written as:

$x \equiv 3 \pmod 5, \quad x \equiv 6 \pmod 7, \quad x \equiv 2 \pmod 9.$

The first congruence gives x = 5k + 3, where k is an integer. Substituting this into the second congruence gives $5k + 3 \equiv 6 \pmod 7 \implies 5k \equiv 3 \pmod 7$ . Since $5\equiv -2 \pmod 7$ , $-2k \equiv 5k \equiv 3 \equiv 10 \pmod 7$ , so by cancellation we have $k \equiv -5 \equiv 2 \pmod 7$ . Writing k = 7j+2, we get x = 5k + 3 = 35j + 13.

Substituting this into the third congruence, we get $35j + 13 \equiv 2 \pmod 9$ so

$-j \equiv 35j \equiv -11 \pmod 9 \implies j \equiv 2 \pmod 9.$

Write j = 9i+2 and this gives x = 35j + 13 = 315i + 83. ♦

Problem 2 : Find all integers x such that $x^2 \equiv 74 \pmod {125}$ .

Solution : Since 125 = 5³, we shall solve this congruence modulo successive powers of 5. First, we get $x^2 \equiv 4 \pmod 5$ . This is easily solved by checking: $x \equiv 2, 3 \pmod 5$ . We consider the case where $x \equiv 2 \pmod 5$ , i.e. x = 5k+2.

Solving for the next power: $(5k+2)^2 \equiv 24 \pmod {25}$ . Expanding, we get:

$25k^2 + 20k + 4 \equiv 24 \pmod {25} \implies 20k \equiv 20 \pmod {25} \implies 4k \equiv 4 \pmod 5.$

By cancellation, we get $k \equiv 1 \pmod 5$ . Thus k = 5j+1 so x = 25j + 7. Substituting this into the congruence $x^2 \equiv 74 \pmod {125}$ , we get:

$350j + 49 \equiv 74 \pmod {125} \implies 14j \equiv 1 \pmod 5.$

Thus $j \equiv 4 \pmod 5$ . Writing j = 5i + 4, we get x = 125i + 107. ♦

[ Question : what about the case $x \equiv 3 \pmod 5$ ? ]

Problem 3 : Find the remainder when 3²⁰¹¹ is divided by 13.

Solution : Note that $3^3 = 27 \equiv 1 \pmod {13}$ . Thus, we get:

$3^{2011} = (3^3)^{670} \times 3 \equiv 1^{670} \times 3 \pmod {13}.$

Hence the answer is 3.♦

Problem 3 thus inspires us to ask the following question: given a and m to find an n > 0 such that $a^n \equiv 1 \pmod m$ . The case where m is prime is given below.

Fermat’s Little Theorem : If p is prime and a is an integer not divisible by p, then $a^{p-1} \equiv 1 \pmod p$ .

To prove this, we use the fact that every integer is congruent to exactly one of {0, 1, …, p-1} modulo p. Now consider the following modulo p:

$1 \times a, 2 \times a, \dots, (p-1)\times a \pmod p,$

expressed as an element in {1, …, p-1} (0 is excluded since they are not divisble by p). We write $i \times a \equiv c_i \pmod p$ , where $i = 1,2,\dots, p-1$ and each $1 \le c_i \le p-1$ . Furthermore no two c_i‘s are identical since

$c_i = c_j \implies (i - j)a \equiv 0 \pmod p \implies i - j \equiv 0 \pmod p,$

since a is not divisible by prime p. Thus, the c_i‘s run through each element of {1, 2, …, p-1} exactly once. Multiplying all the congruence relations together we obtain:

$(a) \times (2a) \times \dots \times ((p-1)a) \equiv 1 \times 2 \times \dots \times (p-1) \mod p$

or $(p-1)! a^{p-1} \equiv (p-1)! \pmod p$ . By cancellation (since p is prime), we have $a^{p-1} \equiv 1 \pmod p$ . ♦

Posted in Notes | Tagged basic, notes, number theory | Leave a comment

Number Theory Notes (22 Oct 2011) – Part I

Posted on October 28, 2011 by limsup

Background required: none.

For the first lecture, we shall look at congruence and modular arithmetic. Many of you may have already known (at least on an intuitive level) that square integers can only end in 0, 1, 4, 5, 6, 9; that the product of two odd numbers is odd; that it’s possible to compute the last digit of (say) $3^{2011}$ without since the last digit of $3^n$ goes in cycles. Here, we shall develop the theory behind it and use it to solve some problems later.

We need a language to state something like “n has remainder 5 when divided by 8″. This is where modular arithmetic comes in.

Definition : if a, b, m are integers, we write $a \equiv b \pmod m$ if a-b is a multiple of m; i.e. if a-b = mk for some integer k. In English, we say “a is congruent to b modulo m”.

Thus, saying “n has remainder 5 when divided by 8″ is the same as $n \equiv 5 \pmod 8$ . [ Exercise in definition: what does it mean to say $a \equiv b \pmod 0$ ? ] To do anything useful with this notation, we need to develop its properties. First, some very basic ones.

Let a, b, c, m be integers. Then the following hold:

We always have $a \equiv a \pmod m$ .
If $a \equiv b \pmod m$ , then $b \equiv a \pmod m$ .
If $a \equiv b \pmod m$ and $b \equiv c \pmod m$ , then $a \equiv c \pmod m$ .

We shall leave out their proofs since they’re really easy. [ E.g. to prove the third property, we have $a \equiv b \pmod m \implies a-b = mj$ and $b \equiv c \pmod m \implies b-c = mk$ for some integers j and k; thus, $a-c = m(j+k) \implies a \equiv c \pmod m$ . ]

The crux of these three properties is that on a purely symbolic level, the notation $a \equiv b \pmod m$ behaves like equality. Thus, we can write without restraint something like

$-5 \equiv 1 \equiv 7 \equiv -11 \equiv \ldots \pmod 6$

thanks to the third property above.

The next three properties tell us that the notation is consistent with respect to arithmetic operations.

Let a, b, c, d, m be integers. Then the following hold:

If $a \equiv b \pmod m$ and $c \equiv d \pmod m$ then $a+c \equiv b+d \pmod m$ .
If $a \equiv b \pmod m$ and $c \equiv d \pmod m$ then $ac \equiv bd \pmod m$ .
If $a \equiv b \pmod m$ then $a^n \equiv b^n \pmod m$ for all n = 1, 2, 3, …

The proofs are as follows. For (4) and (5), we can write a – b = mj and c – d = mk for some integers j and k. Thus:

$(a+c) - (b+d) = (a-b) + (c-d) = m(j+k) \implies a+c \equiv b+d \pmod m.$

$ac - bd = a(c-d) + d(a-b) \implies a+c \equiv b+d \pmod m.$

For (6), we use the known factorisation: for any positive integer n, we can factor the polynomial

$X^n - Y^n = (X - Y) (X^{n-1} + X^{n-2}Y + \dots + XY^{n-2} + Y^{n-1}).$

In particular, this gives $a^n - b^n = (a-b)(a^{n-1} + \dots + b^{n-1})$ which is a multiple of m. So our proof is done.

Finally, while the above properties already suffice, the following may come in useful.

(Cancellation) If $ac \equiv bc \pmod m$ , and (c, m) = 1 (here, (x, y) is the greatest common divisor, or highest common factor, of integers x and y), then $a \equiv b \pmod m$ .

The proof requires Bezout’s identity : if (c, m) = 1, then we can write cx + my = 1 for some integers x and y. For example, if c = 5, m = 8, then we can write x = -3, y = 2. Thus, multiplying this identity by a–b then gives:

(a – b)cx + (a – b)my = (a – b).

Since $ac \equiv bc \pmod m$ , the (a – b)c is a multiple of m, so the first term is divisible by m. Clearly, the second term is also divisible by m. Thus, the RHS is divisible by m so $a \equiv b \pmod m$ . QED.

If c and m have a common factor > 1, then cancellation fails. E.g. pick m = 6, a = 4, b = 2 and c = 9. Then $4 \times 9 \equiv 2 \times 9 \pmod 6$ but $4 \not\equiv 2 \pmod 6$ .

Coming up next: some applications of modular arithmetic.

Posted in Notes | Tagged basic, congruence, modular arithmetic, notes, number theory | Leave a comment

Homework (22 Oct 2011)

Posted on October 27, 2011 by limsup

Here’re the problems:

A square integer N ends in 4 identical digits d in its decimal representation, where $1 \le d \le 9$ . Find all possible values of d. For each admissable value of d, find a possible N.
N is a perfect square whose second-to-last digit is odd. What can its last digit be?
Find all positive integers (x, y) for which $\frac 1 x - \frac 1 y = \frac 1 6$ .
Solve for $y^4 = x^4 + 45x^2$ , where x and y are positive integers.
Prove that the congruence $x^2 \equiv 1 \pmod {2^r}$ , $r \ge 3$ has exactly 4 solutions modulo $2^r$ .

That’s all. 🙂

Posted in Homework | Tagged homework, number theory | Leave a comment

Mathematics and Such

Order of an Element Modulo m and Applications – Part I

Homework (29 Oct 2011)

Number Theory and Calculus/Analysis

Example 1

Example 2

Example 3

Explanation

Number Theory Notes (22 Oct 2011) – Part III

Number Theory Notes (22 Oct 2011) – Part II

Number Theory Notes (22 Oct 2011) – Part I

Homework (22 Oct 2011)

Recent Posts

Archives

Categories

Meta

Pages