Problems & Puzzles: Puzzles

Puzzle 1133 Get another proof A few weeks ago Sebastián Martín Ruiz raised the following conjecture: Let p a prime number and q=2p+1 If 2^(q-1)=4^p=1(mod q) then q is prime and therefore p is a Sophie Germain prime Q) This conjecture has already been proven by someone, could you get other proofs?

---

Miguel Pineda Martín sent on May 17, 2023, a proof for this Puzzle and conjecture from Sebastián Martín Ruiz. Here is his proof.

***

On July 20, 2023, Ken Wilke wrote:

Attached is my “alternate” proof for Problem 1133. While I use the same idea regarding order of an element, I preferred to use the relation 4^x==1(mod q). Also I used a different mechanism to achieve the contradiction establishing the desired result.

A few weeks ago Sebastián Martín Ruiz raised the following conjecture:
Let p a prime number and q=2p+1
If 2^(q-1)=4^p=1(mod q) then q is prime and therefore p is a Sophie Germain
prime
Q) This conjecture has already been proven by someone, could you get other
proofs?
Solution:
Proof: For p=2, we have q = 5 which is prime and 2^(q-1)= 4^p == 1(mod q). For p=3,
we have q = 7 which is prime and 2^(q-1)= 4^p == 1(mod q). Thus W.L.O.G. we can
assume that p > 3 so that q >=7.
Suppose that q is composite. Then there primes t1, t2, …, tk where ti , tj for i < j for
integers I and j. Then
q = t1^e1*t2^e2*… * tk^ek for integers e1, e2,…, ek. (1)
Then phi(q) = {t1^(e1-1)*(t1-1)}* {t2^(e2-1)*(t2-1)}* … *{tk^(ek-1)*(tk-1)} (2)
where phi(q) is Euler’s phi function.
Then since q is divisible by the primes t1, t2, …, tk we have the inequalities
3<= t1 < t2<, …,<tk , (q/3) = (2p+1)/3 < p. (3)
Then for i = 1,2,…,k we have gcd(ti, p) = gcd(ti-1,p) = 1 since each of the integers ti and
ti-1 are less than p and relatively prime to p. Then for i = 1, 2, …,k, each integer of the
form ti^e1-1)*(ti-1)can be composed from the integers ti and ti-1, each of which is
relatively prime to p. Hence for i = 1, 2, …,k, (ti^ei-1)*(ti-1) is relatively prime to p.
Hence gcd(p, phi(q))=1 and p does not divide phi(q).
Now since gcd(4,q) =1, let g denote the the order of 4 (mod q): i.e. g is the smallest
integer such that 4^g == 1 (mod q). Then g must divide phi(q). Furthermore g=1 implies
that q = 3 which contradicts our choice of q and p. If g > 1, then g is a divisor of phi(q). Let
p = m*g +r for some integers m and r with g > r>=0. Then 4^p ==4^(g*m + r) ==4^r
==1(mod q). Hence r=0 since otherwise it contradicts the choice of g. If r=0, then g = p
and p divides phi(q) contrary to our finding that gcd(p, phi(q)) =1.
Hence q = 2p+1 must be prime.

 

***