Prime Numbers in Linear Patterns

(Difference between revisions)
 Revision as of 01:25, 5 December 2012 (edit)← Previous diff Revision as of 00:02, 8 December 2012 (edit) (undo)Next diff → Line 19: Line 19: Proof. Proof. Given any prime number $p$, assume that $p$ is neither congruent to 1 (mod 30) nor $q$ (mod 30) for every prime $q$ less than 30. Then $p$ is congruent to $x$ (mod 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 * 7 =49$, which is greater than 30). Thus, $x=2^a3^b5^c$, where $a,b,c >=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=30*n+2^a3^b5^c$, where $n$ is an integer greater than or equal to 1. Then, $p=30*n+2^a3^b5^c=(2*3*5)n+2^a3^b5^c$. $p$ is then equal to one of $2(3*5*n+2^{a-1}3^b5^c$ or $3(2*5*n+2^a3^{b-1}5^c)$ or $5(2*3*n+2^a3^b5^{c-1})$, which contradicts $p$ being a prime number. Thus, $p \equiv 1 \pmod {30}$ or $p \equiv q \pmod {30}$. Given any prime number $p$, assume that $p$ is neither congruent to 1 (mod 30) nor $q$ (mod 30) for every prime $q$ less than 30. Then $p$ is congruent to $x$ (mod 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 * 7 =49$, which is greater than 30). Thus, $x=2^a3^b5^c$, where $a,b,c >=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=30*n+2^a3^b5^c$, where $n$ is an integer greater than or equal to 1. Then, $p=30*n+2^a3^b5^c=(2*3*5)n+2^a3^b5^c$. $p$ is then equal to one of $2(3*5*n+2^{a-1}3^b5^c$ or $3(2*5*n+2^a3^{b-1}5^c)$ or $5(2*3*n+2^a3^b5^{c-1})$, which contradicts $p$ being a prime number. Thus, $p \equiv 1 \pmod {30}$ or $p \equiv q \pmod {30}$. - - - |AuthorName=Iris Yoon |AuthorName=Iris Yoon |Field=Algebra |Field=Algebra |InProgress=No |InProgress=No }} }}

Revision as of 00:02, 8 December 2012

Prime numbers in table with 180 columns

Prime numbers marked in a table with 180 columns

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.

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

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 (mod 30) nor $q$ (mod 30) for every prime $q$ less than 30. Then $p$ is congruent to $x$ (mod 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 * 7 =49$, which is greater than 30). Thus, $x=2^a3^b5^c$, where $a,b,c >=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=30*n+2^a3^b5^c$, where $n$ is an integer greater than or equal to 1. Then, $p=30*n+2^a3^b5^c=(2*3*5)n+2^a3^b5^c$. $p$ is then equal to one of $2(3*5*n+2^{a-1}3^b5^c$ or $3(2*5*n+2^a3^{b-1}5^c)$ or $5(2*3*n+2^a3^b5^{c-1})$, which contradicts $p$ being a prime number. Thus, $p \equiv 1 \pmod {30}$ or $p \equiv q \pmod {30}$.

Teaching Materials

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

Have questions about the image or the explanations on this page?