Dirichlet ' s Theorem

$$p / ( p-1 ) ! + \left(\frac{a}{p}\right)  a^{(p-1)/2}$$

Proof.
Consider the equation $Ax \equiv a \bmod p$ with $A, x \in \{ 1,2, \cdots p-1\}$,

Case $\left(\frac{a}{p}\right)=-1$
In this case $x$ and $A$ are different members of the set $\{ 1,2, \cdots p-1\}$, there are $(p-1)/2$ distinct pairs $(A, x) $ and pairwise multiplication gives the following identity: $( p-1 ) ! = a^{(p-1)/2}$.

Case $\left(\frac{a}{p}\right)=1$
In this case $a$ is a quadratic residue of $p$ so there are two pairs where $x$ and $A$ are equal members of the set $\{ 1,2, \cdots p-1\}$, there are $(p-3)/2$ distinct pairs $(A, x) $ and pairwise multiplication gives the following identity: $\frac {( p-1 ) ! }{k (p-k)}= a^{(p-3)/2}$.
Now $k( p-k) = kp - k^2 \equiv -a \bmod p $.  Another pairwise multiplication gives the following identity: $( p-1 ) ! = - a^{(p-1)/2}$.

Combining both cases and replacing the sign with the Legendre symbol gives $$p / ( p-1 ) ! + \left(\frac{a}{p}\right)  a^{(p-1)/2}.$$

Diophantus of Alexandria

Diophantus (+/- 250 AD) of Alexandria has been called 'the father of algebra' and an entire branch of mathematics has been named after him, the study of Diophantine Equations. The most famous problem in this field 'Diophantine Equations' is Fermat's 'Last Theorem'. Fermat was reading Diophantus' comments on the Pythagoran theorem when he conjectured that for an exponent n > 2, the equation \[ x^n + y^n = z^n \] has no integer solutions. This theorem was considered the hardest open problem in mathematics until solved by Andrew Wiles in 1994. Diophantus work was lost to the Western world for thousand years.

Anyway, I thought about Diophantus when I came across this beautiful equation which has an infinite number of integer solutions \[ x^3 + y^3 + z^3 = x^2 +y^2 + z^2.\]

Conceptual knowledge maps for mathematics

About working and studying, the main topic of this blog: well, it is no longer an option. It is mandatory, society needs people who are committed to their jobs and invest in their lifetime education. Everything changes at an ever faster pace and it is thus our responsibility to stay of value in all of our dynamics.  It is an issue we must align regularly.

Studying in a particular field will gradually align your life to your new interests. For example, I have recently, more or less -landed- in a job where some of my colleagues are mathematicians. In fact, a lot of the work I do involves mathematics. More about that in posts to come.

Everything changes. So do study skills. And a vast amount of tools for computer aided learning is now available. From MIT lectures via YouTube to software for flash cards to sophisticated knowledge databases for personal use. I would like to mention two items I have found recently.

InfoRapid Knowledge Builder is a graphical tool to document conceptual knowledge maps, free for personal use at http://www.buildyourmap.com/. ( Before this I used Mindjet and TheBrain. ) I am working on a map with topics in Analytical Number Theory.

Another item I found is a book. It is called On Course, Strategies for success in College and Life. ( And if you work and study read the title as Strategies for successful combining work and study.) The book is packed with information. It is not a book you should read once but it is a companion you can use, consult, for years. I have the Study Skills Plus edition.

355 / 113

355 / 113 = 3.141592.....

How would you -prove- that this is the best approximation of pi using only integers less than 1000 ? We can use a 'By Cases' / Brute Force approach and utilize a computer to go through all the possible quotients. Even going through a million of them is a piece of cake nowadays. I wonder if there is a computer-free approach. - Even with a computer its an interesting problem. I.e. what's the shortest program to prove it. The fastest? Go visit Project Euler and you'll be amazed what clever programmers can do in their favorite language. Even if, or especially if, you are a programmer yourself. Amaze yourself. Or take the challenge...

Greatest Common Divisor - GCD

Jan van der Meiden created a graph that shows if the GCD of an integer pair is larger than one by coding the intersection dark versus white when the integers are relatively prime.

Through this graph shimmer numerous patterns.

Have a look here at his site: http://nodus.no.de/gcd01.html

Riemann Hypothesis ( Video )

Very well done video about the history, and the implications of the RH.

M381 'Challenge Exercise' - Revisited

Sorry, Paddy and Jobidaker for the late reply. ( Auto-accepting comments has its drawbacks too. )

My solution for the 1/2, 1/3, 1/5 and 1/7 case is the following. Follow the pattern for the solution to the general case. Click to enlarge pic.

Please let me know if you think a smaller number qualifies.

M381 'Challenge Exercise'

Each Open University M381 Number Theory booklet has a number of 'challenge exercises'. This is one of them.

Half of the number we are looking for is a square, a third of the number is a cubic and lastly a fifth is a fifth power. Find a number satisfying these properties.

Solution on request.

Dreaming of ( massive parallel ) computing power

Or: Numbers divisible by seventeen (17)

I am looking at properties of decimal numbers consisting of only 1s and 0s. Here is a sample of them which are divisible by 17.

\begin{array}{l}
100000001100000000001000100000100000010010 \\
100000001000001000000100110000000000100010 \\
1000000000010001000000010000000100000100000010010 \\
1000000000010001000001000000100100000001000000010 \\
10000001001000000010000000110000000000100010 \\
10000001001100000000001000100000001000000010
\end{array}

Again, these are just ordinary decimal numbers consisting of only ones and zeros. They are all divisible by seventeen (17). Divided by 17 they are:

\begin{array}{l}
5882353005882352941235300000005882353530 \\
5882353000000058823535300588235294123530 \\
58823529412353000000000588235300000005882353530 \\
58823529412353000000058823535300000000058823530 \\
588235353000000000588235300588235294123530 \\
588235353005882352941235300000000058823530
\end{array}

I really wonder where this track might bring me. Do I ( we ) have control over it, or is there some invisible hand leading us?

I do most of my calculations on computers a geek would frown at today but were dreaming of only five years ago. What is computing power? - Since I am not a gamer I thought that I never needed a high-end PC. Now, I think I need a whole wall of them. Serious. It's kind of crazy, isn't it. More of this madness in future posts, I promise.

Thoughts about number theory (1)

Has it ever happened to you that you skipped a proof because no matter how hard you tried you simply "didn't get it"? - Or worse, that you had to learn an algorithm but the 'why' wasn't given, let alone a proof. - Mathematics may be hard and difficult but at the end of the day you should 'own' the theorems. Where ownership stands for the notion that you could have created the theorem, in principle, yourself. Or look at ownership at this way: browse through a mathematics book that you studied two or three years ago, or even longer. Everything in it looks really simple because slowly over the years, you took ownership of that particular subject of mathematics.

When I am stalled on a particular topic or proof, I simply accept the proposition knowing that somehow my brain is working on it. It is a better alternative than remaining stalled. It is possible though that you are stalled because the author decided to leave out 'a few details'. Some topics in number theory, for example, are simple if you look at it from a group theory perspective. The author then has to decide if his proposed audience has already studied group theory or not. And even then his publisher may decide otherwise because from his perspective the audience should be made as large as possible.

Number Theory may be called the Queen of Mathematics the Queen needs a lot of help from the 'people'. There is analytical, algebraic, combinatorial and computational number theory and I wouldn't be surprised if there are a few more. The theory of prime numbers and group theory are strongly interconnected for example. Numbers are among the first mathematical objects that man studied but is a number an object? Unlike graphs, sets and geometric or topological shapes numbers don't really exist. Even groups exist, not just as sets, but they are part of nature itself in the form of symmetries everywhere. What -is- one? Like the one in 'one apple'? I argue that 'number' is a property like color, and the rest is just physics.

What about 'God invented the integers', 'Number theory is beautiful' and so on? The truth is that man invented a God that supposedly invented the integers. I have been studying number theory for a while now, and I haven't found its beauty yet. Just open problems, a lot of open problems everywhere. - Inspector Columbo would call that loose ends. And for him that is proof of human error. - That these open problems are a challenge is another issue.

M381 - Challenge Exercise

In the Open University course Number Theory and Mathematical Logic the additional exercises sections of the workbooks are complemented with several 'challenge exercises'. This is one of them.

Let $n$ be an odd positive integer.
Prove that there are $\tau(n)$ ways of writing $n$ as a sum of consecutive positive integers.
For example, if $n=9$, $\tau(9)=3$ because $9$ has three divisors $1,3,9$ and the three sums are: $9$, $4+5$ and $2+3+4$.

To be continued.

Solving quadratic congruence equations in Mathematica

This is as yet the last post in the LQR series. If you are only interested in -solving- ( quadratic ) congruence equations then this is the way to do it in Mathematica:

As a general Diophantic equation:
In[1]:= Reduce[x^2==123456+1299709 k,{x,k},Integers]

Out[1]= (C[1]\[Element]Integers&&x==427784-1299709 C[1]&&k==140800-855568 C[1]+1299709 C[1]^2)||(C[1]\[Element]Integers&&x==871925-1299709 C[1]&&k==584941-1743850 C[1]+1299709 C[1]^2)

Or slightly more elegant as a pure congruence equation ( thanks to: Mr. Wizard ):
In[2]:= Reduce[x^2 == 123456, x, Modulus -> 1299709]

Out[2]= x == 427784 || x == 871925

Shanks-Tonelli algorithm for solving quadratic modular equations

M381 unit 6 is about the Law of Quadratic Reciprocity. An application of the LQR is solving quadratic modular equations like: $$x^2 \equiv 499 \ \text{mod(617)}.$$ M381 contains a method that can fast determine if that equation is solvable. It does not contain however a fast algorithm for finding the actual solutions. One such algorithm is the Shanks-Tonelli algorithm and can be found on Planet Math which as often gives a much clearer presentation than the messy Wikipedia-entry.

See also: Tutorial for Quadratic Equations

Quadratic reciprocity in a finite group.

Law of Quadratic Reciprocity

Let $p$ and $q$ be distinct odd primes. Then $$\displaystyle \left({\frac p q}\right) \left({\frac q p}\right) = \left({-1}\right)^{\frac {\left({p-1}\right) \left({q-1}\right)} 4}$$ where $\displaystyle \left({\frac p q}\right)$ and $\displaystyle \left({\frac q p}\right)$ are defined as the Legendre Symbol $\displaystyle \left({\frac{a}{p}}\right) := a^{\frac{(p-1)}{2}} \pmod p$.

Gauss considered his work on the Quadratic Reciprocity Law among his major achievements. I don't 'get that', not now anyway, that's a call for more study on the topic.

Now and then, when I browse through papers, or otherwise, I find an interesting mathematical paper... ( that I can actually read ). Actually, I was browsing through a book called Reciprocity Laws, from Euler to Eisenstein by Franz Lemmermeyer, it contains more than 100 proofs of the Quadratic Reciprocity Law. I hoped to find a proof I could appreciate by it's beauty. Although most proofs are based on Gauss's Lemma ( as the proof in M381 ) but there are proofs in other realms of mathematics like Group Theory. Group Theory -as we know it today- did not exist in Gauss's time. That's why I am going to spend some time studying the following paper 'Quadratic reciprocity in a finite group.'

About M381 (1)

Regular readers of this blog know that I have a sort-of rage-button like the Hulk: it is called MathCad. Thank God, I have the anti-dote almost always open and ready: Mathematica. I am not going to repeat why MathCad is a danger to your mental health, but I have to press the MathCad button at least once.

In almost all mathematics courses you can do at the Open University there is software involved. They either deliver a standard package, or ship custom software especially developed for the course ( i.e. MT365 ). The house-package of the Mathematics Department of the Open University is MathCad, version 2001. I have argued that MathCad alone is a reason -not- to choose for the Open University. What a disgrace...

( Calming down. )

They do however recognize that software, computers, tools are relevant in mathematics. Especially in Number Theory computers are used in active research. Another area where they use software in active research is: mathematical logic. Stronger: research in Number Theory is impossible without computers.

These facts are not even mentioned in M381. There are many open source tools available for Number Theory, even more for Mathematical Logic. Not a word about it in M381. One, if not -the- reason is the fact that course development in the Open University is done in a project organization. A project is created with the objective to create course X which will then be used for the next 10 or so years. It is exactly the opposite of what one would expect of a university education. It is not reasonable to expect the Open University to be at the forefront of mathematical research. Simply because other universities in the UK have that role. But it is reasonable to expect more than a static expose of 19th century Gauss number theory and early 20th century logic from Church, Turing and Goedel. In fact, the field is presented as abstract and of theoretical importance only. But Number Theory and Mathematical Logic are extremely relevant and applicable in many industries! But I did not learn that from the course and that is sad.

It took me a lot of work but I found some relevant learning tools in the fields of number theory and mathematical logic. More about those later in this blog.

(*) - I may have misunderstood the concept of 'University' in the UK. I think many universities in the UK are what we call in the Netherlands 'schools'. They deliver professionals with a degree in all fields through excellent education but they don't do research and so on. They don't add to the body of knowledge. They process and transfer knowledge. That description fits the Open University as well. - A marketing issue is that students like to have a 'university' education. And marketing people love empty heads boxes, they have a fancy word for it too: the 'packaging'. Does that make sense?

Prime?

A prime p is a number with two positive divisors: 1 and p. Note how this definition nicely excludes 1 which has only one positive divisor. Then the primes are: $$2,3,5,7,11,13,17,19,23,29, \cdots$$
Wait! What about:
$$ 5 = -i \cdot (1 + 2i) \cdot (2 + i)$$
This is an example of a factorization in the quadratic field of Gaussian Integers. It is therefore not enough to say that a number is prime. Primality is relative in relation to the number field.

The mathematician Lamé thought to have cracked Fermat's Last Theorem in 1847. Needless to say that his proof contained an error. He overlooked the fact that prime factorization was not unique in a number system he used in his proof.

In Mathematica factorization is done with:

FactorInteger[n],
factorization using Gaussian integers is done with:

FactorInteger[5, GaussianIntegers -> True].

Perrin numbers

Let $P(0)=3, P(1)=0, P(2)=2$ and $$P(k) = P(k-2) + P(k-3.)$$ These numbers are called the Perrin numbers. They have the interesting property that $\mod{[P(k), k]} = 0$ in almost all cases when k is prime. ( Otherwise we would have found a true prime generator! ). In any case the property holds until $k=271441.$ Interesting, isn't it? See the table below for the first 40 Perrin numbers.

k	P[k]	Mod[P[k],k]	PrimeQ
2	2	0	True
3	3	0	True
4	2	2	False
5	5	0	True
6	5	5	False
7	7	0	True
8	10	2	False
9	12	3	False
10	17	7	False
11	22	0	True
12	29	5	False
13	39	0	True
14	51	9	False
15	68	8	False
16	90	10	False
17	119	0	True
18	158	14	False
19	209	0	True
20	277	17	False
21	367	10	False
22	486	2	False
23	644	0	True
24	853	13	False
25	1130	5	False
26	1497	15	False
27	1983	12	False
28	2627	23	False
29	3480	0	True
30	4610	20	False
31	6107	0	True
32	8090	26	False
33	10717	25	False
34	14197	19	False
35	18807	12	False
36	24914	2	False
37	33004	0	True
38	43721	21	False
39	57918	3	False
40	76725	5	False

Exercise

For $x,y \in \mathbf{N}$ the equation: $$x^2 - 11 y^2 = 1.$$ has infinite many solutions. Find three solutions other than $(10,3)$.

Hint: Use continued fractions.

Fermat on arithmeticians

Thanks to Sol Robeson ( in PI ) we call mathematicians who lost it "numerologists".

In 1657, Fermat challenged William Brouncker, of Castle Lynn in Ireland, and John Wallis to find integral solutions to the equations $$x^2 − 151y^2 = 1$$ and $$x^2 − 313y^2 = −1.$$ He ( Fermat ) cautioned them not to submit rational solutions because even the lowest type of arithmetician could devise such answers.

"An Introduction to Diophantine Equations, A Problem-Based Approach, Andreescu, Andrica & Cucurezeanu, Springer 2010"

Considering that Fermat used the qualification the lowest type of arithmetician there must have been a ranking in the computational branch those days. Until at least WW2, a computer, was the job description of someone who did "computational work" in banking, insurance, trading, logistics and what have you. Jobs like that exist even now, think of the actuarial sciences, but most of them if not all require a degree in mathematics. I am not sure but I suppose that in Fermat's days there must have been people responsible for the basic addition and multiplication type of calculations. Fermat called them "arithmeticians, of the lowest kind".

I am speculating of course. Fermat could have been a terrible arrogant man looking down on the working class. Considering that he was not a mathematician himself but that he wrote, on his own initiative, letters to the great minds of his time says at least something of his self-image.

Link: My previous post on Fermat

Continued fractions (3)

Each rational number can be represented as a finite continued fraction (FCF) and each FCF represents a rational number. We have seen how to calculate the rational number from a given FCF, in this post we show how to calculate the FCF for any rational number.

For example, the FCF representation of $\frac{17}{13}$ can be calculated as follows:

$a$	$q$	$b$	$r$
$17$	$1$	$13$	$4$
$13$	$3$	$4$	$1$
$4$	$4$	$1$	$0$

The value of the FCF is contained in the second column from top to bottom: $\frac{17}{13}$ is $\left[ 1,3,4 \right]$. This is clearly an application of Euclid's algorithm for calculating the GCD of two integers. The algorithm for calculating the GCD stops at row $3$ but by adding one more row containing $4 = 4 \times 1 + 0$ the column containing the FCF is complete.

See also:
- Continued fractions (1)
- Continued fractions (2)
- Continued fractions (2a)