Difference between revisions of "Prime Numbers in Linear Patterns"

From Math Images
Jump to: navigation, search
 
(47 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
{{Image Description
 
{{Image Description
|ImageName=Prime numbers in table with 180 columns
+
|ImageName=Prime numbers in a table with 180 columns
 
|Image=Screen shot 2012-10-01 at 2.49.15 PM.png
 
|Image=Screen shot 2012-10-01 at 2.49.15 PM.png
|ImageIntro=Prime numbers marked in a table with 180 columns
+
|ImageIntro=Create a table with 180 columns and write down positive integers from 1 in increasing order from left to right, top to bottom. When we mark the prime numbers on this table, we obtain the linear pattern as shown in the figure.
|ImageDescElem=Arranging natural numbers in a particular way and marking the prime numbers can lead to interesting patterns. For example, consider a table with 180 columns and infinitely many rows. Write positive integers in increasing order from left to right, and top to bottom. If we mark all the prime numbers, we get a pattern shown in the figure. We can see that prime numbers show patterns of vertical line segments.
+
|ImageDescElem=Arranging natural numbers in a particular way and marking the prime numbers can lead to interesting patterns. For example, consider a table with 180 columns and infinitely many rows. Write positive integers in increasing order from left to right, and top to bottom. If we mark all the prime numbers, we get a pattern shown in the figure. We can see that prime numbers show patterns of vertical line segments, which implies that the prime numbers only appear on certain columns.
|ImageDesc=Instead of studying a table with 180 columns, we will study a table with 30 columns.
+
|ImageDesc=Instead of studying a table with 180 columns, we will study a table with 30 columns, as shown in [[#1|Image 1]].
  
{{Anchor|Reference=1|Link=[[Image:primes30.png|Image 1|thumb|250px|left]]}}
+
{{Anchor|Reference=1|Link=[[Image:primes30.png|Image 1|thumb|100px|left]]}}
  
 +
==Construction==
  
The prime spiral was discovered by Stanislaw Ulam (1909-1984) in 1963 while he was doodling on a piece of paper during a science meeting. Starting with 1 in the middle, he wrote positive numbers in a grid as he spiraled out from the center, as shown in [[#1|Image 1]]. He then circled the prime numbers, and the prime numbers showed patterns of diagonal lines as shown by the grid in [[#2|Image 2]]. The grid in [[#2|Image 2]] is a close-up view of the center of the main image such that the green line segments and red boxes in the center of the main image line up with those in the grid.
+
First, create a table with 30 columns and sufficiently many rows. Write all positive integers starting from 1 as one moves from left to right, and top to bottom. Then, each row will start with a multiple of 30 added by 1, such as 1, 31, 61, 91, 121, ... . If we mark the prime numbers in this table we get [[#2|Image 2]].
  
A larger Ulam spiral with 160,000 integers and 14,683 primes is shown in the main image. Black dots indicate prime numbers. In addition to diagonal line segments formed by the black dots, we can see white vertical and horizontal line segments that cross the center of the spiral and do not contain any black dots, or prime numbers. There are also white diagonal line segments that do not contain any prime numbers. Ulam spiral implies that there is some order in the distribution of prime numbers.
+
{{Anchor|Reference=2|Link=[[Image:Irisprime.jpg|Image 2|thumb|700px|none]]}}
 +
 
 +
==Properties==
 +
'''Theorem 1.'''
 +
All prime numbers appear on columns that have a <math>1</math> or a prime number on its top row. In other words, for every prime number <math>p </math>, either <math> p \equiv 1\pmod {30}</math>, or there exists a prime number <math> q </math> less than <math>30</math> such that <math> p \equiv q \pmod {30} </math>.
 +
 
 +
''Proof.''
 +
 
 +
Given any prime number <math> p</math>, assume that <math>p </math> is neither congruent to <math> 1 \pmod {30}</math> nor <math> q \pmod {30}</math> for every prime <math> q</math> less than <math> 30</math>. Then,
 +
:<math> p  \equiv x \pmod {30}</math>,
 +
where <math> x </math> is some integer less than <math>30 </math> that is not <math> 1 </math> and not a prime. Prime factorization of <math> x </math> must contain one of <math>2, 3,</math> and <math>5</math>. (If the prime factorization of <math>x </math> did not contain any of <math>2, 3,</math> or <math> 5</math>, then the smallest possible value of <math> x</math> will be <math>7 \cdot 7 =49 </math>, which is greater than <math>30</math>). Thus,
 +
:<math> x=2^a3^b5^c</math>,
 +
where <math> a,b,c \ge 0</math>, and at least one of <math> a,b,c</math> is greater than <math>0</math>.
 +
 
 +
Since <math> p </math> is congruent to <math> x</math>, we can write <math>p </math> as <math> p=30n+x=30n+2^a3^b5^c</math>, where <math>n </math> is an integer greater than or equal to 1. Then,
 +
:<math>p=30n+2^a3^b5^c=(2 \cdot 3 \cdot 5)n+2^a3^b5^c </math>.
 +
<math> p</math> is then equal to one of <math> 2(3 \cdot 5 \cdot n+2^{a-1}3^b5^c)</math>, <math> 3(2 \cdot 5 \cdot n+2^a3^{b-1}5^c)</math>, and <math>5(2 \cdot 3 \cdot n+2^a3^b5^{c-1})</math>. This contradicts that <math>p </math> is a prime number. Thus, <math> p \equiv 1 \pmod {30}</math> or <math> p \equiv q \pmod {30} </math>, for some prime number <math>q</math> less than <math>30</math>.<math> \Box </math>
 +
 
 +
 
 +
However, the statement does not generalize to other integer modulo groups. For instance, consider a table with <math>60</math> columns. The number <math>49</math> appears on the first row, and <math>49</math> is not a prime number. However, the column containing <math>49 </math> will contain other prime numbers, such as <math>109</math>.
 +
 
 +
Moreover, not all integers that are congruent to <math>1 \pmod {30} </math> or <math> q \pmod {30}</math>, where <math> q </math> is a prime number less than <math>30</math>, are prime numbers. For instance, <math>49</math>, which is congruent to <math>19 \pmod {30} </math>, is not a prime number, but <math>49</math> still appears on the same column as<math>19</math>. Let's call the columns that have a <math>1</math> or a prime number greater than <math>5</math> on its top row as prime-concentrated columns. One can observe that for all composite numbers that appear on these prime-concentrated columns, say <math>49,77,91,119,121,133,143,161,169,..., </math> all prime factors must be greater than or equal to <math>7</math>. In other words, these composite numbers do not have <math>2, 3, </math>or <math>5</math> as a prime factor.
 +
 
 +
 
 +
'''Theorem 2.'''
 +
Composite numbers that appear on prime-concentrated columns do not have <math>2,3,</math> or <math>5</math> as a prime factor.
 +
 
 +
''Proof.''
 +
 
 +
Let <math> x </math> be a composite number that appears on a prime-concentrated column, and assume that <math> x </math> has at least one of <math>2, 3,</math> or <math>5</math> as a prime factor. Since <math> x </math> appears on the prime-concentrated column, <math> x </math> can be written as
 +
:<math> x=30n+k </math>,
 +
where <math> n </math> is a positive integer, and <math> k =1</math>or <math>k</math> is a prime number such that <math> 7 \le k \le 29.</math> If <math> x </math> had <math>2</math> as a prime factor, <math> k </math> must also have <math>2</math> as a factor because <math>30</math> has <math>2</math> as a factor. This contradicts the fact that <math> k =1</math> or <math> k</math> is a prime number such that <math> 7 \le k \le 29</math>. The same argument works for the case when <math> x </math> has <math>3</math> or <math>5</math> as prime factors.<math> \Box </math>
 +
 +
 
 +
Another pattern to notice is that the prime-concentrated columns seem symmetric about the column that contains <math>15</math>, which leads to the following observation.
 +
 
 +
 
 +
'''Theorem 3.'''
 +
If <math> p </math> is a prime number less than<math> 30 </math> and if <math> p </math> is not equal to <math>2,3, </math> or <math>5,</math> then <math>30-p</math> is a prime number.
 +
 
 +
''Proof.''
 +
 
 +
Let <math> p </math> be a prime number less than <math>30</math> that is not equal to <math>2, 3, </math>or <math>5</math>. Let <math> q=30-p </math>. If <math> q </math> were not a prime, then <math> q </math> must have <math>2, 3,</math> or <math>5</math> as a prime factor. Since <math> p=30-q </math>, <math> p </math> will also be divisible by <math>2, 3,</math> or <math>5</math>, contradicting our condition that <math> p </math> is a prime number. <math> \Box </math>
 +
 
 +
 
 +
One can also observe that each prime-concentrated column seems to contain infinitely many prime numbers. In fact, such observation is consistent with Dirichlet's Theorem in Arithmetic Progressions.
 +
 
 +
 
 +
'''Dirichlet's Theorem On Primes In Arithmetic Progressions'''
 +
 
 +
Let <math>a,N</math> be relatively prime integers. Then there are infinitely many prime numbers <math>p</math> such that <math>p \equiv a \pmod {N} </math>.
 +
 
 +
 
 +
The proof of Dirichlet's Theorem is not written on this page. One can easily note that Dirichlet's Theorem implies that each prime-concentrated column contains infinitely many prime numbers.
 
|AuthorName=Iris Yoon
 
|AuthorName=Iris Yoon
|Field=Algebra
+
|Field=Number Theory
 +
|ToDo=Q: would it be possible to generalize the above statements to any subgroup of the integers modded by the product of first n primes?
 +
 
 +
i.e, can we generalize above statements to the case where we create a table with more number of columns?
 
|InProgress=No
 
|InProgress=No
 
}}
 
}}

Latest revision as of 06:44, 3 January 2013


Prime numbers in a table with 180 columns
Screen shot 2012-10-01 at 2.49.15 PM.png
Field: Number Theory
Image Created By: Iris Yoon

Prime numbers in a table with 180 columns

Create a table with 180 columns and write down positive integers from 1 in increasing order from left to right, top to bottom. When we mark the prime numbers on this table, we obtain the linear pattern as shown in the figure.


Basic Description

Arranging natural numbers in a particular way and marking the prime numbers can lead to interesting patterns. For example, consider a table with 180 columns and infinitely many rows. Write positive integers in increasing order from left to right, and top to bottom. If we mark all the prime numbers, we get a pattern shown in the figure. We can see that prime numbers show patterns of vertical line segments, which implies that the prime numbers only appear on certain columns.

A More Mathematical Explanation

Instead of studying a table with 180 columns, we will study a table with 30 columns, as shown in [[#1 [...]

Instead of studying a table with 180 columns, we will study a table with 30 columns, as shown in Image 1.

Image 1


Construction

First, create a table with 30 columns and sufficiently many rows. Write all positive integers starting from 1 as one moves from left to right, and top to bottom. Then, each row will start with a multiple of 30 added by 1, such as 1, 31, 61, 91, 121, ... . If we mark the prime numbers in this table we get Image 2.

Image 2


Properties

Theorem 1. All prime numbers appear on columns that have a 1 or a prime number on its top row. In other words, for every prime number p , either  p \equiv 1\pmod {30}, or there exists a prime number  q less than 30 such that  p \equiv q \pmod {30} .

Proof.

Given any prime number  p, assume that p is neither congruent to  1 \pmod {30} nor  q \pmod {30} for every prime  q less than  30. Then,

 p  \equiv x \pmod {30},

where  x is some integer less than 30 that is not  1 and not a prime. Prime factorization of  x must contain one of 2, 3, and 5. (If the prime factorization of x did not contain any of 2, 3, or  5, then the smallest possible value of  x will be 7 \cdot 7 =49 , which is greater than 30). Thus,

 x=2^a3^b5^c,

where  a,b,c \ge 0, and at least one of  a,b,c is greater than 0.

Since  p is congruent to  x, we can write p as  p=30n+x=30n+2^a3^b5^c, where n is an integer greater than or equal to 1. Then,

p=30n+2^a3^b5^c=(2 \cdot 3 \cdot 5)n+2^a3^b5^c .

 p is then equal to one of  2(3 \cdot 5 \cdot n+2^{a-1}3^b5^c),  3(2 \cdot 5 \cdot n+2^a3^{b-1}5^c), and 5(2 \cdot 3 \cdot n+2^a3^b5^{c-1}). This contradicts that p is a prime number. Thus,  p \equiv 1 \pmod {30} or  p \equiv q \pmod {30} , for some prime number q less than 30. \Box


However, the statement does not generalize to other integer modulo groups. For instance, consider a table with 60 columns. The number 49 appears on the first row, and 49 is not a prime number. However, the column containing 49 will contain other prime numbers, such as 109.

Moreover, not all integers that are congruent to 1 \pmod {30} or  q \pmod {30}, where  q is a prime number less than 30, are prime numbers. For instance, 49, which is congruent to 19 \pmod {30} , is not a prime number, but 49 still appears on the same column as19. Let's call the columns that have a 1 or a prime number greater than 5 on its top row as prime-concentrated columns. One can observe that for all composite numbers that appear on these prime-concentrated columns, say 49,77,91,119,121,133,143,161,169,..., all prime factors must be greater than or equal to 7. In other words, these composite numbers do not have 2, 3, or 5 as a prime factor.


Theorem 2. Composite numbers that appear on prime-concentrated columns do not have 2,3, or 5 as a prime factor.

Proof.

Let  x be a composite number that appears on a prime-concentrated column, and assume that  x has at least one of 2, 3, or 5 as a prime factor. Since  x appears on the prime-concentrated column,  x can be written as

 x=30n+k ,

where  n is a positive integer, and  k =1or k is a prime number such that  7 \le k \le 29. If  x had 2 as a prime factor,  k must also have 2 as a factor because 30 has 2 as a factor. This contradicts the fact that  k =1 or  k is a prime number such that  7 \le k \le 29. The same argument works for the case when  x has 3 or 5 as prime factors. \Box


Another pattern to notice is that the prime-concentrated columns seem symmetric about the column that contains 15, which leads to the following observation.


Theorem 3. If  p is a prime number less than 30 and if  p is not equal to 2,3, or 5, then 30-p is a prime number.

Proof.

Let  p be a prime number less than 30 that is not equal to 2, 3, or 5. Let  q=30-p . If  q were not a prime, then  q must have 2, 3, or 5 as a prime factor. Since  p=30-q ,  p will also be divisible by 2, 3, or 5, contradicting our condition that  p is a prime number.  \Box


One can also observe that each prime-concentrated column seems to contain infinitely many prime numbers. In fact, such observation is consistent with Dirichlet's Theorem in Arithmetic Progressions.


Dirichlet's Theorem On Primes In Arithmetic Progressions

Let a,N be relatively prime integers. Then there are infinitely many prime numbers p such that p \equiv a \pmod {N} .


The proof of Dirichlet's Theorem is not written on this page. One can easily note that Dirichlet's Theorem implies that each prime-concentrated column contains infinitely many prime numbers.




Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.





Future Directions for this Page

Q: would it be possible to generalize the above statements to any subgroup of the integers modded by the product of first n primes?

i.e, can we generalize above statements to the case where we create a table with more number of columns?




If you are able, please consider adding to or editing this page!


Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.