mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-10-29, 22:32   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default Weird occurrence

Over in Seventeen or Bust forum, someone tested 2*11^n+1 numbers for primality, and discovered the following:

2*11^11325+1
2*11^11325+1 Divides Phi(11^11325,2)
2*11^13359+1
2*11^13359+1 Divides Phi(11^13359,2)
2*11^11325+1
2*11^11325+1 Divides Phi(11^11325,2)
2*11^13359+1
2*11^13359+1 Divides Phi(11^13359,2)


They were wondering if anyone can explain this?

Please note: I have no idea what Phi means, I'm just trying to help out my friends, so if someone could give me something that I can simply copy and paste, I would be very grateful.
jasong is offline   Reply With Quote
Old 2006-10-31, 06:03   #2
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Can you give a link to the original topic in Seventeen or Bust forum? Thanks.
maxal is offline   Reply With Quote
Old 2006-10-31, 21:24   #3
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

2×13×43 Posts
Default

Here is the thread:
http://www.free-dc.org/forum/showthread.php?t=3146
philmoore is offline   Reply With Quote
Old 2006-11-05, 05:06   #4
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Please explain what is the function Phi(x,y).
maxal is offline   Reply With Quote
Old 2006-11-12, 00:16   #5
XYYXF
 
XYYXF's Avatar
 
Jan 2005
Minsk, Belarus

24×52 Posts
Default

http://mathworld.wolfram.com/CyclotomicPolynomial.html
XYYXF is offline   Reply With Quote
Old 2006-11-12, 22:24   #6
maxal
 
maxal's Avatar
 
Feb 2005

111111002 Posts
Default

Quote:
Originally Posted by jasong View Post
Over in Seventeen or Bust forum, someone tested 2*11^n+1 numbers for primality, and discovered the following:

2*11^11325+1
2*11^11325+1 Divides Phi(11^11325,2)
2*11^13359+1
2*11^13359+1 Divides Phi(11^13359,2)
2*11^11325+1
2*11^11325+1 Divides Phi(11^11325,2)
2*11^13359+1
2*11^13359+1 Divides Phi(11^13359,2)


They were wondering if anyone can explain this?
Let p=2*11^k+1 be prime (note that k must be odd, otherwise p is divisible by 3). The fact that p divides Phi((p-1)/2,2) follows from the fact that the multiplicative order of 2 modulo p is (p-1)/2.

Note that 2 is a square modulo p (the Legendre symbol (2/p)=1), implying that the multiplicative order of 2 divides (p-1)/2=11^k.
The multiplicative order is smaller than (p-1)/2 only if 2 is the 11-th power modulo p. Being the 11-th power is less likely than not-being (roughly in 10 times). Perhaps, there exist examples when 2 is the 11-th power modulo p but they are harder to find.

Last fiddled with by maxal on 2006-11-12 at 22:29
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Dr Nicely's 1st occurrence Prime Gaps rudy235 Prime Gap Searches 192 2020-02-06 09:48
Weird Dubslow YAFU 14 2016-01-06 19:34
This is weird... Isn't it? guido72 PrimeNet 18 2015-06-11 16:18
A 1 in 1,852 occurrence! NBtarheel_33 Data 27 2009-03-25 03:33
something very weird ixfd64 PrimeNet 1 2008-10-16 18:19

All times are UTC. The time now is 11:42.

Tue Jan 19 11:42:13 UTC 2021 up 47 days, 7:53, 0 users, load averages: 2.06, 1.84, 1.71

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.