Weird occurrence

[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?

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.

[maxal]

Can you give a link to the original topic in Seventeen or Bust forum? Thanks.

[philmoore]

Here is the thread:
http://www.free-dc.org/forum/showthread.php?t=3146

[maxal]

Please explain what is the function Phi(x,y).

[XYYXF]

http://mathworld.wolfram.com/CyclotomicPolynomial.html

[maxal]

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.