Tag Archives: primes

Prime Number Problem

Standard

Following is a problem about prime factorization of the sum of consecutive odd primes. (source: problem 80 from The Green Book of Mathematical Problems)

Prove that the sum of two consecutive odd primes is the product of at least three (possibly repeated) prime factors.

The first thing to observe is that sum of odd numbers is even, hence the sum of two consecutive odd primes will be divisible by 2. Let’s see factorization of some of the examples:

3 + 5 = 2\times 2 \times 2
5 + 7 = 2 \times 2\times 3
7+11 = 2 \times 3\times 3
11+13 = 2 \times 2 \times 2 \times 3
13+17 = 2 \times 3 \times 5
17+19 = 2\times 2\times 3 \times 3
19+23 = 42 = 2\times 3\times 7
23+29 = 52 = 2\times 2 \times 13

Now let p_n and p_{n+1} be the consecutive odd primes, then from above observations we can conjecture that either p_n+p_{n+1} is product of at least three distinct primes or p_n+p_{n+1}= 2^k p^\ell for some odd prime p such that k+\ell \geq 3.

To prove our conjecture, let’s assume that p_n+p_{n+1} is NOT a product of three (or more) distinct primes (otherwise we are done). Now we will have to show that if p_n+p_{n+1}= 2^k p^\ell for some odd prime p then k+\ell \geq 3.

If \ell = 0 then we should have k\geq 3. This is true since 3+5=8.

Now let \ell > 0. Since k\geq 1 (sum of odd numbers is even), we just need to show that k=1, \ell=1 is not possible. On the contrary, let’s assume that k=1,\ell = 1. Then p_n+p_{n+1} = 2p. By arithmetic mean property, we have

\displaystyle{p_n < \frac{p_n+p_{n+1}}{2}} = p <p_{n+1}

But, this contradicts the fact that p_n,p_{n+1} are consecutive primes. Hence completing the proof of our conjecture.


This is a nice problem where we are equating the sum of prime numbers to product of prime numbers. Please let me know the flaws in my solution (if any) in the comments.

Advertisements

Childhood Maths – II

Standard

I found two documents that I was very proud of as a child. Both were the result of trying to understand the kind of things Ramanujan did in free time, a result of the little AMTI books I read as a child. I will share the second document in this post and the other one was in the previous post.

Following document was created in MS Word on my old Windows XP desktop. The calculations were done using some Microsoft advanced calculator:

primes

I was not happy with the result though since the pattern didn’t continue which was supposed to continue according to Ramanujan.

Prime Polynomial Theorem

Standard

I just wanted to point towards a nice theorem, analogous to the Prime Number Theorem, which is not talked about much:

# irreducible monic polynomials with coefficients in \mathbb{F}_q and of degree n \sim \frac{q^n}{n}, for a prime power q.

The proof of this theorem follows from Gauss’ formula:

# monic irreducible polynomialswith coefficients in \mathbb{F}_q and of degree n = \displaystyle{\frac{1}{n}\sum_{d|n}\mu\left(\frac{n}{d}\right)q^d}, by taking d=n.

 

For details, see first section of this: http://alpha.math.uga.edu/~pollack/thesis/thesis-final.pdf

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

Popular-Lonely primes understood

Standard

While reading standup mathematician Matt Parker‘s book Things to Make and do in Fourth Dimension, I found answer (on pp. 146) to the question I raised 7 months ago.

wp-1474049555336.jpg

When the grid happens to be a multiple of 6 wide, suddenly all primes snap into dead-straight lines. All primes (except 2 and 3) are one more or less than a multiple of 6. (© Matt Parker, 2014)

He also proves the following surprising theorem:

The square of every prime number greater than 3 is one more than a multiple of 24.

Let p be an odd prime not equal to 3. Now we subtract one from the square of this prime number. Therefore, we wish to prove that p^2-1=(p-1)(p+1) is a multiple of 24.

Note that, p^2-1 is a product of two even numbers. In particular, one of these two even numbers must be a multiple of 4, as they are consecutive even numbers and every other even number is divisible by 4. Hence we conclude that p^2-1 is divisible by 8. 

Observe that exactly one of three consecutive numbers, p-1,p,p+1 must be divisible by 3. Since p is an odd prime different from 3, one of p-1 or p+1 must be divisible by 3. Hence we conclude that p^2-1 is divisible by 3.

Combining both the conclusions made above, we complete proof of our statement (since 2 and 3 are coprime).

Edit[19 April 2017]: Today I discovered that this theorem is exercise 68 in “The USSR Olympiad Problem Book“.

Primes: popular and lonely

Standard

ulam While doodling in class, I made a 10 x 10 grid and filled it with numbers from 1 to 100. The motivations behind 10 x 10 grid was human bias towards the number 10.

New Doc 10_1

Then inspired by Ulam Spiral, I started creating paths (allowing diagonal, horizontal and vertical moves) starting from the smallest number. Following paths emerged:

  • 2→ 3 →13 → 23
  • 2 → 11
  • 7 → 17
  • 19 → 29
  • 31 → 41
  • 37 → 47
  • 43 → 53
  • 61 → 71
  • 73 → 83
  • 79 → 89

So, longest path is of length 4 and others are of length 2.

The number 2 is special one here, since it leads to two paths. I will call such primes, with more than one paths, popular primes.

Now, 5, 59, 67 and 97 don’t have any prime number neighbour. I will call such primes, with no neighbour, lonely primes.

I hope to create other b \times b grids filled with 1 to b^2 natural numbers written in base b. Then will try to identify such lonely and popular primes.

If you find this idea interesting, please help me to create such grids.

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=2x=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.