"Prime in all bases"?

Uncwilly · 2004-09-08, 13:13

I know what primes are, I know what bases are, but how does the base make a difference if a number is prime?

wblipp · 2004-09-08, 13:59

Quote:

Originally Posted by Uncwilly

I know what primes are, I know what bases are, but how does the base make a difference if a number is prime?

The phrase probably should have been "pseudo-prime to all (many?) bases." In this context, "base" would mean the "a" value when calculating a^n-1 mod n.

Uncwilly · 2004-09-08, 15:18

So it doesn't mean a base like: 13₁₀ or 12₁₁ or 11₁₂ or 10₁₃

Maybeso · 2004-09-10, 23:48

In this context, I think that it does mean a base like 11010011₁₃

The phrase "Prime in all bases" refers to a search for numbers which remain prime when you change the base from the smallest legal up to some n, without actually converting it. A number consisting of 0's & 1's would start in base 2.

There are examples on the web, in the primenumbers list at yahoo.
100001000101111111101101₂ = 8675309, prime
100001000101111111101101₃ = ?
100001000101111111101101₄ = ?
100001000101111111101101₅ = ?
100001000101111111101101₆ = ?

(I would give an actual example, but this message window will time out ...

)

Terence Schraut · 2006-11-21, 18:07

Another twist on "Prime in all bases". As "everyone" knows each number base has its own set of digits. For multi-digit numbers in that base these digits can be divided into two groups- one group which are never prime if a number ends one of those digits, and a group multi-digit primes are "permitted" to end in.
A prime number is "Prime in all bases" in the sense no matter which base you express a multi-digit prime number in, it will always end in a premissable digit for multi-digit primes in that paticular base. On the other hand, no matter how many different bases a number ends in a premissible digit for multi-digit primes, if these is a base where that number ends in a non-permitted digit, it is not prime.

alpertron · 2006-11-22, 15:15

Quote:

Originally Posted by Maybeso

In this context, I think that it does mean a base like 11010011₁₃

The phrase "Prime in all bases" refers to a search for numbers which remain prime when you change the base from the smallest legal up to some n, without actually converting it. A number consisting of 0's & 1's would start in base 2.

There are examples on the web, in the primenumbers list at yahoo.
100001000101111111101101₂ = 8675309, prime
100001000101111111101101₃ = ?
100001000101111111101101₄ = ?
100001000101111111101101₅ = ?
100001000101111111101101₆ = ?

(I would give an actual example, but this message window will time out ...

)

Not all numbers of the form "string of zeros and ones in any order base n" can be prime:

Let's suppose that there are k ones in that string.

Using base k+1 we get the following value:

$\large \sum_{i=1}^{k} (k+1)^{r_i}$

Since $(k+1)^{r_i} - 1$ is multiple of $(k+1) - 1\, =\, k$ we find that $(k+1)^{r_i} \eq 1\,\pmod k$ .

$\large \sum_{i=1}^{k} (k+1)^{r_i}\,\eq\,\sum_{i=1}^{k} 1\,\eq\,0\,\pmod k$

This means that the number is multiple of $k$ so it cannot be prime.

ATH · 2006-11-22, 16:19

These numbers are all prime in base 2 to 10:

110100000010101111110001010011001110001
111000001000000100011110000000111000111101
111100000011101111101001101111000110000101
10001110100101110001001001001101011011111001
10010001000100111001000100100010111000000111
110001001101010000000010110010011110010110001
110100001001000010000010010001101000000100001
110101101100000010010001111000111001111110001
110101111101110111100111111010000110011011111
111000100111010100011000010001101001100100001
1001001011000000011111000001111100001001001001

Example:

1001001011000000011111000001111100001001001001₂=40338853446217 (prime)
1001001011000000011111000001111100001001001001₃=3068384663551105704493 (prime)
1001001011000000011111000001111100001001001001₄=1257608695782515405809258561 (prime)
1001001011000000011111000001111100001001001001₅=28650989406788706784246828140751 (prime)
1001001011000000011111000001111100001001001001₆=104429167454184682110486807513218329 (prime)
1001001011000000011111000001111100001001001001₇=107319808663410009085057221813360961657 (prime)
1001001011000000011111000001111100001001001001₈=43641382631776836084899974327476091617793 (prime)
1001001011000000011111000001111100001001001001₉=8739952731757538744486007088622324643616171 (prime)
1001001011000000011111000001111100001001001001₁₀ (prime)

mfgoode · 2006-11-22, 16:40

Quote:

Originally Posted by alpertron

Not all numbers of the form "string of zeros and ones in any order base n" can be prime:

Let's suppose that there are k ones in that string.

Using base k+1 we get the following value:

$\large \sum_{i=1}^{k} (k+1)^{r_i}$

Since $(k+1)^{r_i} - 1$ is multiple of $(k+1) - 1\, =\, k$ we find that $(k+1)^{r_i} \eq 1\,\pmod k$ .

$\large \sum_{i=1}^{k} (k+1)^{r_i}\,\eq\,\sum_{i=1}^{k} 1\,\eq\,0\,\pmod k$

This means that the number is multiple of $k$ so it cannot be prime.

Alpertron:
Please pardon my ignorance but I can follow your reasoning until the last line.
Please explain even if it is elementary.

BTW: Is there a method of factorising and finding primes by coupling the Binomial theorem with Fermat's little theorem which is being used today?
I have an article that explains the method with examples.

Mally

alpertron · 2006-11-22, 16:52

Quote:

Originally Posted by ATH

Example:

1001001011000000011111000001111100001001001001₂=40338853446217 (prime)
[...]
1001001011000000011111000001111100001001001001₁₀ (prime)

Using the same example:

1001001011000000011111000001111100001001001001₂₀ = 35188770686542026899458825635495936275940966400512064008001 is multiple of 19.

This can be done without base conversion by noticing that the string has 19 ones and applying the reasoning I showed in my previous post.

ATH · 2006-11-22, 17:20

I understand your reasoning, no number can be prime in ALL bases. I was just showing some examples in response to Maybeso's post.

That particular number fails allready at base 11:
1001001011000000011111000001111100001001001001₁₁=72945288900070500848531287367874506645605685989 = 6703*10882483798309786789278127311334403497777963

alpertron · 2006-11-22, 18:27

I used that number just as an example. I know it is difficult to find numbers that are primes for several bases.

As an extension of the reasoning done above, I will show that a general number cannot be prime in all bases (not only in the case of only zeros and ones as shown above).

Let k be any divisor of the sum of the digits (it can also be the sum of the digits, but those numbers are smaller).

So $\sum_{i=1}^{m} d_i \eq 0 \,\pmod k$

Using base k+1 we get the following value:

$\large \sum_{i=1}^{m} d_i(k+1)^{r_i}$

Since $(k+1)^{r_i} - 1$ is multiple of $(k+1) - 1\, =\, k$ we find that $(k+1)^{r_i} \eq 1\,\pmod k$ .

$\large \sum_{i=1}^{m} d_i(k+1)^{r_i}\,\eq\,\sum_{i=1}^{m} d_i\,\eq\,0\,\pmod k$

This means that the number is multiple of $k$ so it cannot be prime.

2004-09-08, 13:13	#1
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 9784₁₀ Posts	"Prime in all bases"? I know what primes are, I know what bases are, but how does the base make a difference if a number is prime?

2006-11-22, 17:20	#10
ATH Einyen Dec 2003 Denmark 6127₈ Posts	I understand your reasoning, no number can be prime in ALL bases. I was just showing some examples in response to Maybeso's post. That particular number fails allready at base 11: 1001001011000000011111000001111100001001001001₁₁=72945288900070500848531287367874506645605685989 = 670310882483798309786789278127311334403497777963 Last fiddled with by ATH on 2006-11-22 at 17:28*

2006-11-22, 18:27	#11
alpertron Aug 2002 Buenos Aires, Argentina 2×683 Posts	I used that number just as an example. I know it is difficult to find numbers that are primes for several bases. As an extension of the reasoning done above, I will show that a general number cannot be prime in all bases (not only in the case of only zeros and ones as shown above). Let k be any divisor of the sum of the digits (it can also be the sum of the digits, but those numbers are smaller). So $\sum_{i=1}^{m} d_i \eq 0 \,\pmod k$ Using base k+1 we get the following value: $\large \sum_{i=1}^{m} d_i(k+1)^{r_i}$ Since $(k+1)^{r_i} - 1$ is multiple of $(k+1) - 1\, =\, k$ we find that $(k+1)^{r_i} \eq 1\,\pmod k$ . $\large \sum_{i=1}^{m} d_i(k+1)^{r_i}\,\eq\,\sum_{i=1}^{m} d_i\,\eq\,0\,\pmod k$ This means that the number is multiple of $k$ so it cannot be prime. Last fiddled with by alpertron on 2006-11-22 at 18:31

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!"	wildrabbitt	Miscellaneous Math	11	2015-03-06 08:17
Prime-Related History: Leibniz' "Universal Language Based on Primes"	ewmayer	Math	10	2007-03-02 12:47
Speeding up double checking when first test returns "prime"	Unregistered	PrimeNet	16	2006-02-28 02:00
Oh noes! The "42nd Mersenne prime" isn't prime!	ixfd64	Lounge	7	2005-04-03 19:27
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?	nitai1999	Software	7	2004-08-26 18:12

2004-09-08, 15:18	#3
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 2638₁₆ Posts	So it doesn't mean a base like: 13₁₀ or 12₁₁ or 11₁₂ or 10₁₃

2004-09-10, 23:48	#4
Maybeso Aug 2002 Portland, OR USA 2·137 Posts	In this context, I think that it does mean a base like 11010011₁₃ The phrase "Prime in all bases" refers to a search for numbers which remain prime when you change the base from the smallest legal up to some n, without actually converting it. A number consisting of 0's & 1's would start in base 2. There are examples on the web, in the primenumbers list at yahoo. 100001000101111111101101₂ = 8675309, prime 100001000101111111101101₃ = ? 100001000101111111101101₄ = ? 100001000101111111101101₅ = ? 100001000101111111101101₆ = ? (I would give an actual example, but this message window will time out ... )

2006-11-21, 18:07	#5
Terence Schraut Oct 2006 7 Posts	Another twist on "Prime in all bases". As "everyone" knows each number base has its own set of digits. For multi-digit numbers in that base these digits can be divided into two groups- one group which are never prime if a number ends one of those digits, and a group multi-digit primes are "permitted" to end in. A prime number is "Prime in all bases" in the sense no matter which base you express a multi-digit prime number in, it will always end in a premissable digit for multi-digit primes in that paticular base. On the other hand, no matter how many different bases a number ends in a premissible digit for multi-digit primes, if these is a base where that number ends in a non-permitted digit, it is not prime.

2006-11-22, 16:19	#7
ATH Einyen Dec 2003 Denmark 3⁵·13 Posts	These numbers are all prime in base 2 to 10: 110100000010101111110001010011001110001 111000001000000100011110000000111000111101 111100000011101111101001101111000110000101 10001110100101110001001001001101011011111001 10010001000100111001000100100010111000000111 110001001101010000000010110010011110010110001 110100001001000010000010010001101000000100001 110101101100000010010001111000111001111110001 110101111101110111100111111010000110011011111 111000100111010100011000010001101001100100001 1001001011000000011111000001111100001001001001 Example: 1001001011000000011111000001111100001001001001₂=40338853446217 (prime) 1001001011000000011111000001111100001001001001₃=3068384663551105704493 (prime) 1001001011000000011111000001111100001001001001₄=1257608695782515405809258561 (prime) 1001001011000000011111000001111100001001001001₅=28650989406788706784246828140751 (prime) 1001001011000000011111000001111100001001001001₆=104429167454184682110486807513218329 (prime) 1001001011000000011111000001111100001001001001₇=107319808663410009085057221813360961657 (prime) 1001001011000000011111000001111100001001001001₈=43641382631776836084899974327476091617793 (prime) 1001001011000000011111000001111100001001001001₉=8739952731757538744486007088622324643616171 (prime) 1001001011000000011111000001111100001001001001₁₀ (prime)