# Prime Consequences

Standard

Most of us are aware of the following consequence of Fundamental Theorem of Arithmetic:

There are infinitely many prime numbers.

The classic proof by Euclid is easy to follow. But I wanted to share the following two analytic equivalents (infinite series and infinite products) of the above purely arithmetical statement:

• $\displaystyle{\sum_{p}\frac{1}{p}}$   diverges.

For proof, refer to this discussion: https://math.stackexchange.com/q/361308/214604

• $\displaystyle{\sum_{n=1}^\infty \frac{1}{n^{s}} = \prod_p\left(1-\frac{1}{p^s}\right)^{-1}}$, where $s$ is any complex number with $\text{Re}(s)>1$.

The outline of proof,   when $s$ is a real number, has been discussed here: http://mathworld.wolfram.com/EulerProduct.html

# Numbers and Logic

Standard

I am a big fan of number theory. I find the answer to Hilbert’s Tenth Problem fascinating. I was introduced to this problem, a couple of years ago, via the documentary titled : “Julia Robinson and Hilbert’s Tenth Problem“, here is the trailer:

You can read more about it here. Also for the sake of completeness, let me state Hilbert’s Tenth Problem:

Does there exist an algorithm to determine whether a given Diophantine equation has a solution in rational integers?

In 1970, Yuri Matiyasevich completed the solution of this problem by using the concept of Turing Machine. This short video provides a nice overview about Turing Machines in general

The answer to Hilbert’s Tenth Problem problem is

No such algorithm exists.

This interplay of number theory and logic is really interesting, isn’t it? But I can’t discuss solution of Hilbert’s Tenth Problem here, since I have never read it. But there is nice overview at Wikipedia.

I will rather discuss a puzzle from Boris A. Kordemsky’s book which illustrates the idea of this interplay.

Ask a friend to pick a number from 1 through 1000. After asking him/her ten questions that can be answered yes or no, you tell him/her the number. What kind of question?

The key to the solution is that 2 to the tenth power is 1024 (that is, over 1000). With each question you knock out half the remaining numbers, and after ten questions only the thought number is left.

I welcome you to think of a number and write the corresponding yes/no questions as a comment below.

# Happy Birthday Ramanujam

Standard

Today is 128th birthday of Srinivasa Ramanujam Iyengar.

[Please note that Britishers gave wrong English spelling for his name, they called him “Ramanujan”,  but it should be “Ramanujam” which means  “The younger brother of Lord Rama”]

John Littlewood said (as recalled by G. H. Hardy (1921), in “Obituary Notices: Srinivasa Ramanujan”, Proceedings of the London Mathematical Society 19, p. lvii) :

Every positive integer is one of Ramanujan’s personal friends.

So, let’s talk about numbers on his birthday.

128 is 7th power of 2 and leads to 4th Mersenne Prime ($2^7 - 1=127$ is a prime)

128 is the largest number which is not the sum of distinct squares. [https://oeis.org/A001422]

and here is my present for him:

RAMANUJAM’S MAGIC SQUARE

When I was in High School, I learned making such “Special Date Magic Squares” form P.K. Srinivasan’s (1924-2005) book regarding Ramanujam’s work. [see: https://nrich.maths.org/1380 ]

Magic sum of this square is 69. Thus all rows, columns and diagonals add up to the same total of 69 and today’s date has been placed in first row.

69 is a value of $n$ where $n^2$ and $n^3$ together contain each digit once. Since, $69^2=4761$ and $69^3 = 328509$

Ramanujam also studied “Partition Function”, this function gives the number of ways of writing the integer n as a sum of positive integers, where the order of addends is not considered significant. Observe that, in the magic square above we created 10 distinct 4-partitions of 69. (though 2376 distinct 4-partitions of 69 are possible!!)

Also, the total sum of numbers in our magic square is $69\cdot 4 = 276 = 1^5 + 2^5 + 3^5$

Once more, Happy Birthday Ramanujam!

# Diophantine Equation & Primes

Standard

I stumbled upon following statement on some webpage (don’t have link):

There exist infinitely many integers $n$ such that $n^2 +1$ divides $n!$.

I tried proving it, though not able to prove it but here are my insights:

• Proof by contradiction (the way we show infinite primes) doesn’t work here.
• I need to prove that $\frac{n!}{n^2+1} = k \in \mathbb{N}$ for infinitely many values of $n$, so I should try to express $n^2+1$ in product form (since numerator is already in product form). After writing denominator in product form,  find a condition satisfied by infinitely many values of $n$, which generates infinitely many natural numbers as outcomes of $\frac{n!}{n^2+1}$.

First idea that came to my mind, for factoring the denominator was in terms Gaussian Integers (numbers of form $a+ib$ where $a,b$ are integers and $i = \sqrt{-1}$), but I am not able to proceed in this direction further.

Second idea to generate factors of denominator was to analyze Diophantine equation (i.e. we are concerned with only integer solutions of given equation), of form: $x^2 + 1 = Dy^2$

Here is a theorem from Diophantine equation, which can help me generate factors:

Lemma: Let $p$ be a prime. The diophantine equation: $x^2 - py^2 = -1$ is solvable if and only if $p=2$ or $p\equiv 1 \pmod 4$

Proof: If the considered equation has a solution $(x,y)$, then $p| x^2+1$. Hence either  $p=2$ or  $p \equiv 1 \pmod 4$.

For $p=2$$x=y=1$ is a solution.

We show that there is a solution for each prime $p=4t+1$. Let us study the existence of an integral solution $(x_0,y_0)$ to the wee known diophantine equation: $x_0^2 - py_0^2 = 1$.

Observe that $x_0$ is odd [otherwise, $y_0^2 \equiv py_0^2 \equiv 3 \pmod 4$, but no square leaves a remainder 3 when divided by 4]. Thus in the relation:

$x_0^2 - 1 = (x_0-1)(x_0+1) = py_0^2$

factors $x_0+1$ and $x_0-1$ have greatest common divisor 2, and consequently one of them is a doubled square (to be denoted by $2x^2$) and the other one $2p$ times a square (to be denoted by $2py^2$).

The case $x_0+1 = 2x^2$ and $x_0-1 = 2py^2$ is impossible because it leads to a smaller solution of diophantine equation: $x^2-py^2=1$. [method of infinite descent]

It follows that $x_0-1=2x^2$ , and $x_0+1 = 2py^2$, therefore $x^2-py^2 = -1$

——

Now we return back to main statement.

——

Let $n^2+1 = pm^2$, where $m \in \mathbb{N}$ and $p$ is a prime of  form $p=2$ or $p \equiv1 \pmod 4$.

Now let us consider another result:

Lemma: There are infinitely number of primes of the form $4n+1$.

ProofSuppose $n>1$ is an integer. Let $p$ be the smallest prime divisor of $N$.

We define $N=(n!)^2 +1$.

Since $N$ is odd, $p$ cannot be equal to $2$. It is clear that $p$ is bigger than $n$ (otherwise $p \mid 1$ ).

We know that $p$ has the form $4k+1$ or $4k+3$. Since $p\mid N$ we have:

$(n!)^2 \equiv -1 \pmod p \$

$\Rightarrow (n!)^{p-1} \equiv (-1)^{ \frac{p-1}{2} } \pmod p$.

Using Fermat’s little Theorem we get $(-1)^{ \frac{p-1}{2} } \equiv 1 \pmod p$.

If $p$ was of the form $4k+3$ then $\frac{p-1}{2} =2k+1$ is odd and therefore we obtain $-1 \equiv 1 \pmod p$ or $p \mid 2$ which is a contradiction since $p$ is odd.

Hence, $p$ is of the form $4k+1$, now we can repeat the procedure replacing $n$ with $p$ and produce an infinite sequence of primes of the form $4k+1$.

——

From above lemma, we can say that, $n^2+1 = pm^2$ for infinitely many values of $p$

I have expressed denominator in product form, what remains to prove is that the expression $\frac{n!}{pm^2}$  simplifies to give a natural number as answer.

Now this appears to me as a dead end.

If you discover/know the proof of starting statement please give its outline in comments.

But, the motive of this post is to show the beautiful flowers I observed while searching for a path which leads to given statement.