euler

Last Digit

How would we go about finding the last digit of very large numbers, such as Screen Shot 2017-08-24 at 4.27.22 PM.png ?

There are a variety of different tools that we can use, including modular arithmetic and the Chinese remainder theorem, which I am going to talk about in today’s post.

Pattern Finding

A problem like this can be tackled by listing out the initial expansions of a power in order to determine a pattern. Then, by proving that this pattern holds (often by induction), the last decimal digit of a power can be solved completely. For example, the last digit of various powers of 1 to 9 are:

Screen Shot 2017-08-24 at 4.32.26 PM.png

Source: Brilliant

From this we can determine that:

the last digit of powers of 1 is always 1;
the last digits of powers of 2 repeat in a cycle of 4, 8, 6, 2;
the last digits of powers of 3 repeat in a cycle of 9, 7, 1, 3;
the last digits of powers of 4 alternate between 6 and 4;
the last digit of powers of 5 is always 5;
the last digit of powers of 6 is always 6;
the last digits of powers of 7 repeat in a cycle of 9, 3, 1, 7;
the last digits of powers of 8 repeat in a cycle of 4, 2, 6, 8;
the last digits of powers of 9 alternate between 1 and 9.

Example

Find the last digit of 2^2016.

The last digits of the powers of two repeat in a cycle of 2, 4, 8, 6. Dividing 2016 by 4 we get 504 (with no remainder). Hence the sequence of digits repeats 504 times with no extra entries, so the last digit should be 6.

Modular Arithmetic

The above idea can be expressed more elegantly with modular arithmetic. Finding the last digit of a number is the same as finding the remainder when this number is divided by 10. In general, the last digit of a power in base n is its remainder upon division by n. So, for decimal numbers, we compute mod 10 to find the last digit, mod 100 to find the last two digits, etc.

For example,

Screen Shot 2017-08-24 at 5.22.44 PM.png

Chinese Remainder Theorem

The Chinese Remainder Theorem states that

“if one knows the remainders of the division of an integer $n$ by several integers, then one can determine uniquely the remainder of the division of $n$ by the product of these integers, under the condition that the divisors are pairwise coprime“

– Wikipedia

Applying this theorem, we can find a number mod 2^n and mod 5^n and then combine those results to find that number mod 10^n.

Example

Find the last two digits of 74^540.

Observe that 100 = 4 x 25 and gcd(4,25) = 1. So we can compute 74^540 mod 4 and mod 25, then combine these to find it mod 100.

74^540 ≡ 2^540 x 37^540 ≡ 0 (mod 4)

and

7^540 ≡ (-1)^540 ≡ 1 (mod 25)

The unique solution mod 100 to x ≡ 0 (mod 4), x ≡ 1 (mod 25) is 76, so this is the answer.

Euler’s Theorem

Euler’s Theorem states that

“if n and a are coprime positive integers, then

$a^{\varphi (n)} \equiv 1 \pmod{n}$

where $\varphi (n)$ is Euler’s totient function.”

-Wikipedia

So an exponent b can be reduced modulo φ(n) to a smaller exponent without changing the value of a^b (mod n).

Example

Find the last two digits of 33^42.

φ(100) = 40, so 33^40≡ 1 (mod 100). So, 33^42 ≡ 33^2 (mod 100). This is easier to compute: 33^2 = 1089, so answer is 89.

Binomial Expansion

Another method is to expand the power using the Binomial theorem in such a way that many of the terms vanish mod 10. This is generally only useful when the base of the exponent is of the form 10k +/- 1.

Example

Find the last two digits of 31^25.

After the second term, every term contains at least 2 zeros, and so they vanish mod 100. The first two terms = 751 ≡ 51 (mod 100) and so the last two digits of 31^25 are 51.

Hope you enjoyed this slightly longer post! M x

MATHS BITE: Apéry’s Constant

Apéry’s constant is defined as the number

${\begin{aligned}\zeta (3)&=\sum _{n=1}^{\infty }{\frac {1}{n^{3}}}\\&=\lim _{n\to \infty }\left({\frac {1}{1^{3}}}+{\frac {1}{2^{3}}}+\cdots +{\frac {1}{n^{3}}}\right)\end{aligned}}$

where ζ is the Riemann Zeta Function.

This constant is named after the French mathematician Roger Apéry who proved that it was irrational in 1978. However it is still unknown whether or not it is transcendental.

History

The Basel Problem asked about the convergence of the following sum:
Screen Shot 2017-06-10 at 2.16.05 PM.png

In the 18th century, Leonhard Euler proved that in fact it did – to π^2/6. However, the limit of the following sum remained unknown: Screen Shot 2017-06-10 at 2.19.28 PM.png

Although mathematicians made some progress, including Euler who calculated the first 16 decimal digits of the sum, it was not known whether the number was rational or irrational, until Apéry.

Furthermore, it is currently not known specifically whether any other particular ζ(n), for n odd, is irrational. “The best we’ve got is from Wadim Zudilin, in 2001, who showed that at least one of ζ(5), ζ(7), ζ(9), ζ(11) must be irrational, and Tanguy Rivoal, in 2000, who showed that infinitely many of the ζ(2k+1) must be irrational.”

M x

Prime Number Theorem

Today I thought I’d quickly discuss a extremely important theorem in one of my favourite areas in mathematics: Number Theory (as you can probably tell by the number of posts that I’ve published about primes!).

Perhaps the first property of π(x) – the number of primes less than or equal to x – is that π(x) tends to infinity as x tends to infinity. In other words, the prime numbers are infinite, which was proved by Euclid in “Elements”. A more precise result, established by Euler in 1737, was that the series of reciprocals of the prime numbers:

Screen Shot 2016-10-19 at 6.09.35 PM.png

is a divergent series. In doing so, Euler found an alternative way to prove that there was an infinite number of primes, as if there wasn’t then the series would have a finite value.

The Prime Number Theorem states that if π(x) is the number of primes less than or equal to x, then

Although the notation ~ may be unfamiliar, it simply means that π(x) is asymptotically equal to x/lnx, i.e.

Note that the prime number theorem is equivalent to saying that the nth prime number p_n satisfies the following relationship:

The PNT was proposed by Gauss in 1792 when he was only 15 years old! (Makes you wonder what you’ve been doing with your life so far…) He later refined this estimate to

$\begin{displaymath}\pi(x) \sim \int_2^x \frac{d u}{\ln{u}}.\end{displaymath}$

HAPPY HALLOWEEN! M x

MATHS BITE: The Bridges of Königsberg

In 1735, the city of Königsberg in Prussia (which is now Kaliningrad, Russia) was divided into four sections by the Pregel River. These four sections where connected by seven bridges.

Source: Wikipedia

The Königsberg bridge problem asked whether there was a walk through the city that would cross each bridge once and only once.

In 1736 Euler proved that this walk was not possible, achieving this by inventing a kind of diagram called a network, that is made up of vertices (dots where lines meet) and arcs (lines). His solution was presented to the St. Petersburg Academy in August 1735, and was published in the journal Commentarii academiae scientiarum Petropolitanae in 1741.

Screen Shot 2016-09-16 at 11.19.49 AM.png

Source: Wolfram MathWorld

This was a novel idea; Euler discovered that the physical positions of the sections do not matter, but rather it’s the connections made by the bridges that matters. Hence, by having this intuition Euler opened up a new branch of mathematics: graph theory. Euler describes how:

“. . . this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle.”

So why is such a walk not possible?

Euler showed that the possibility of this walk existing – called a Eulerian path – is dependant on the degrees of the nodes. The degree of a node is how many edges touch it. He found that the necessary condition for this walk to exist is that should have exactly 0 or 2 nodes with an odd degree.

As all four of the nodes in the network of Königsberg have an odd degree, the walk does not exist.

M x

Euler’s Conjecture

The Sum of Powers Conjecture was proposed by Euler in 1769. It states that:

“for all integers $n$ and $k$ greater than 1, if the sum of $n$ $k$ th powers of non-zero integers is itself a $k$ th power, then $n$ is greater than or equal to $k$ .”

This can be more concisely written as:

If $\sum _{i=1}^{n}a_{i}^{k}=b^{k}$ , where $n > 1$ and $a 1, a 2, \dots, a n, b$ are non-zero integers, then $n \geq k$ .

Fermat’s Last Theorem is simply a special case of this conjecture: if, when n=2, $a 1 k + a 2 k = b k$ , then $2 \geq k. Hence, this conjecture can be seen to represent an attempt to generalise Fermat’s Last Theorem.$

Although it is true for n = 3, it was disproved for k = 4 and k = 5. Mathematicians still do not know whether it is true for $k \geq 6$ .

In 1966, L.J. Lander and T. R. Parkin disproved this conjecture in the shortest article in any ‘serious’ mathematical journal (Source), which consisted of merely 2 lines.

Screen Shot 2016-09-06 at 12.45.09 PM.png

This counterexample for k = 5 was found by a direct computer search on a CDC 6600 (a “flagship mainframe supercomputer”).

CDC 6600 | Source: Wikipedia

M x

The Knight’s Tour

A Knight’s Tour is a sequence of moves of a knight on a chessboard such that the knight lands on every square only once. If the knight’s tour ends on the square that it began on, then the tour path is closed. Otherwise, it is open.

Knight’s Tour | Source: Wikipedia

The Knight’s Tour is a common mathematical problem given to computer science students; it is a more general Hamiltonian path problem in graph theory. The Hamiltonian path problem is a problem of “determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) exists in a given graph.”

One of the first mathematicians to analyse this problem was Euler. However, the first procedure for completing the Knight’s Tour was Warnsdorf’s rule, which was described by H.C. von Warnsdorf in 1823.

Warnsdorf’s Rule states that the knight should always move to the square from which the knight will have the “fewest onward moves”. There can be, of course, two squares which have the same number of onward moves, and consequently there are ways to break such ties, for example the methods devised by Pohl and Squirrel.

Is a Knight’s Tour always possible?

Allen Schwenk proved that for any m x n boards, where m is smaller or equal to n, a closed knight tour is always possible if one of the following conditions is met:

m and n are both odd
m = 1, 2 or 4
m=3 and n = 4, 6 or 8

Hope you enjoyed today’s post. M x

The Basel Problem

The Basel Problem is a problem in number theory posed by Pietro Mengoli in 1644, and solved by Leonhard Euler in 1734. As the problem remained open for 90 years, Euler’s solution brought him immediate fame at the age of 28.

The Basel Problem asks the result of the sum

$1+\frac{1}{4}+\frac{1}{9}+\frac{1}{16}+\frac{1}{25}+\frac{1}{36}+...$

i.e. the sum of the inverse of the square numbers.

Screen Shot 2016-08-06 at 10.52.38 AM.png

As there are infinitely many square numbers, this sum has infinitely many terms. It is possible to find the ‘result’ of this sum due to the fact that the sum converges to a particular limiting value as the denominator approaches infinity. Part of the difficulty of solving this series is because it converges very slowly; when n = 10⁶, the result is only accurate to 5 decimal places.

Euler found that the result had the value of:

Screen Shot 2016-08-06 at 10.55.45 AM.png

But how did he do this?

Firstly, recall the Taylor series expansion of sin(x):

$\sin(x)=x-{\frac {x^{3}}{3!}}+{\frac {x^{5}}{5!}}-{\frac {x^{7}}{7!}}+\cdots .$

If we divide by x, this gives us:

${\frac {\sin(x)}{x}}=1-{\frac {x^{2}}{3!}}+{\frac {x^{4}}{5!}}-{\frac {x^{6}}{7!}}+\cdots .$

Applying the Weierstrass factorisation theorem, which states that “entire functions can be represented by a product involving their zeroes” we obtain the expression:

${\begin{aligned}{\frac {\sin(x)}{x}}&=\left(1-{\frac {x}{\pi }}\right)\left(1+{\frac {x}{\pi }}\right)\left(1-{\frac {x}{2\pi }}\right)\left(1+{\frac {x}{2\pi }}\right)\left(1-{\frac {x}{3\pi }}\right)\left(1+{\frac {x}{3\pi }}\right)\cdots \\&=\left(1-{\frac {x^{2}}{\pi ^{2}}}\right)\left(1-{\frac {x^{2}}{4\pi ^{2}}}\right)\left(1-{\frac {x^{2}}{9\pi ^{2}}}\right)\cdots .\end{aligned}}$

If we multiply out this product and collect all x² terms we get:

$-\left({\frac {1}{\pi ^{2}}}+{\frac {1}{4\pi ^{2}}}+{\frac {1}{9\pi ^{2}}}+\cdots \right)=-{\frac {1}{\pi ^{2}}}\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}.$

In the expansion of sin(x)/x the coefficient of x² is -1/(3!). By comparing coefficients and noting that they must be equal on each side, we can equate this as:

$-{\frac {1}{6}}=-{\frac {1}{\pi ^{2}}}\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}.$

Hence, reaching a final result of

$\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}={\frac {\pi ^{2}}{6}}.$

Sources: 1 | 2 | 3

M x

mathsbyagirl

new posts monday and thursday