 mersenneforum.org > Math Weird occurrence
 Register FAQ Search Today's Posts Mark Forums Read 2006-10-29, 22:32 #1 jasong   "Jason Goatcher" Mar 2005 5·701 Posts 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.    2006-10-31, 06:03 #2 maxal   Feb 2005 22·32·7 Posts Can you give a link to the original topic in Seventeen or Bust forum? Thanks.   2006-10-31, 21:24 #3 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 2×13×43 Posts Here is the thread: http://www.free-dc.org/forum/showthread.php?t=3146   2006-11-05, 05:06 #4 maxal   Feb 2005 22×32×7 Posts Please explain what is the function Phi(x,y).   2006-11-12, 00:16 #5 XYYXF   Jan 2005 Minsk, Belarus 24×52 Posts    2006-11-12, 22:24   #6
maxal

Feb 2005

111111002 Posts Quote:
 Originally Posted by jasong 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  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post rudy235 Prime Gap Searches 192 2020-02-06 09:48 Dubslow YAFU 14 2016-01-06 19:34 guido72 PrimeNet 18 2015-06-11 16:18 NBtarheel_33 Data 27 2009-03-25 03:33 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