mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Can 1227133513 be the only composite number matching the conditions? (https://www.mersenneforum.org/showthread.php?t=19393)

 miket 2014-05-29 11:50

Can 1227133513 be the only composite number matching the conditions?

Conditions:

n such that O | n - 1 and O - 1 = 2^x , n ∈ 2N + 1, O = Ord_n(2), x ∈ Z≥0.

Can 1227133513 be the only composite number matching the conditions?

Erick Wong has check up to 10^20, see: [URL="http://math.stackexchange.com/questions/813293/are-there-composite-numbers-matching-the-conditions"] Are there composite numbers matching the conditions?[/URL]

More info of 1227133513: Ord_{1227133513}(2) = 33 and 33 | 2^33 - 1.

 CRGreathouse 2014-05-29 12:46

I suspect he checked only to 2^64 using Jan's list.

Probably there are others but searching seems futile.

 R.D. Silverman 2014-05-29 15:23

[QUOTE=CRGreathouse;374524]I suspect he checked only to 2^64 using Jan's list.

Probably there are others but searching seems futile.[/QUOTE]

On very rough probability grounds one might expect there to be
O(loglog N) examples up to N

 CRGreathouse 2014-05-29 17:48

[QUOTE=R.D. Silverman;374530]On very rough probability grounds one might expect there to be
O(loglog N) examples up to N[/QUOTE]

Abusively assuming the big-O constant to be 1, the expected number of new examples up to 10^25 is 1/4. To get a 95% chance of finding and example you'd need to go above 10^385.

 R.D. Silverman 2014-05-29 20:05

[QUOTE=CRGreathouse;374537]Abusively assuming the big-O constant to be 1, the expected number of new examples up to 10^25 is 1/4. To get a 95% chance of finding and example you'd need to go above 10^385.[/QUOTE]

The constant should be derivable, but offhand I am unsure how to
do it.

 Rich 2014-08-12 00:41

Sorry, I must be confused because n = 601 * 1801 * 6151 = 6657848551 seems to work. This is the same order of magnitude as the other solution quoted so it's unlikely to have been missed. It's less than 10[SUP]10[/SUP] and certainly less than 10[SUP]20[/SUP] that Erick Wong is supposed to have checked to.
I claim that O = 1025 = 2[SUP]10[/SUP] + 1 = 5[SUP]2[/SUP] * 41
2[SUP]1025[/SUP] = 1 mod n
2[SUP]1025 / 5[/SUP] = 5533233944 mod n and 2[SUP]1025 / 41[/SUP] = 33554432 (which seem to have more than their fair share of digit pairs 33, 44 and 55)
This proves that the order of 2 is 1025 as required.
Finally n = 1025 * 6495462 + 1 so O | n-1 as required.

The next solution seems to be 13857901601 = 6151 * 2252951 = 1025 * 13519904 + 1
2[SUP]1025 / 5[/SUP] = 12903300634 mod 13857901601 (hmm.. more digit pairs)
while
2[SUP]1025[/SUP] = 1 mod 13857901601
This proves the order of 2 is 1025 again while n-1 is of the required form.

I believe there are a total of 4079 solutions with O=1025 of which an impressive one (but by no means the largest) is n = 19858924506932274923192217121413840253555986701099656443876494287833804013531009915252291156116144835199447717419022262305584364955410801

Indeed shouldn't any product of the primes where 2 has the required order qualify as a composite of the required form? As the orders get larger, the number of primes with the required order increase as well.

Contrary to what Bob claims, I believe that when we start talking about numbers n where log(log(n)) is not small then these sorts of numbers are actually quite common.

 All times are UTC. The time now is 09:27.