Generator of P but not Q

We start out by looking for possible values that $q$ could be to not have $2$ being a generator, then backtrack and check whether it is a generator for the corresponding $p$ .

$2$ is not a generator modulo $q$ if and only if there exists some smallest number $k < q-1$ where $2^k \equiv 1 \pmod{q}$ . Notice that $k$ must be a factor of $q-1$ - this follows from noting that the remainders modulo $q$ are then cyclic with order $k$ and that $2^{q-1} \equiv 1 \pmod{q}$ , Fermat's Little Theorem. Therefore the cycle repetition of $1$ coincides exactly with $q-1$ , which can only occur if $k$ is a multiple of $q-1$ .

But then, $q-1 = 2p$ , so $k$ can only be $2$ or $p$ . If $k=2$ , then that means $2^2 = 4 \equiv 1 \pmod{q}$ , which only happens when $q=3$ . Otherwise, $k=p$ , which shall be assumed from hereon in to find more suitable values of $q$ . These values occur if and only if $2^p \equiv 1 \pmod{q}$ .

We now use the established fact that there exists a number $x$ such that $x^2 \equiv 2 \pmod{q}$ if and only if $q \equiv \pm 1 \pmod{8}$ .

If $q \neq \pm 1 \pmod{8}$ , suppose $2^p\equiv 1 \pmod q.$ Suppose $g$ is a generator modulo $q$ and $2\equiv g^a \pmod q.$ Then $g^{ap}\equiv 1 \pmod q,$ so $ap$ is a multiple of $q-1=2p.$ Therefore $a$ is even, meaning $2\equiv g^a$ is a square modulo $q,$ a contradiction. So $2^p \neq 1 \pmod{q}$ and $2$ has to be a generator for $q$ . We discard any primes of this sort.

If $q \equiv \pm 1 \pmod{8}$ and we can write $2 \equiv x^2 \pmod{q}$ , then $2^p = x^{2p} = x^{q-1} \equiv 1 \pmod{q}$ , and so $q$ will be a prime of the desired type. It is not known if $p$ will have $2$ as a generator, but this narrows down the possibilities enough for this to be checked by case.

$q \equiv \pm 1 \pmod{8} \Rightarrow p \equiv 3 \pmod{4}$ , so it is desired to seek out primes $p$ where $p \equiv 3 \pmod{4}$ and $2p + 1$ is a prime. A search of every prime under 100 yields the following 4 cases - $(3, 11, 23, 83)$ . $q$ , by the method of choosing, will definitely not have $2$ as a generator, so we only need to check whether $2$ is a generator for these possible values of $p$ . This can be done quickly by noticing that $11 = 2 \times 5 + 1, 23 = 2 \times 11 + 1$ and $83 = 2 \times 41 + 1$ ; with the exception of $23$ , each of these is of the exact same form as the primes $q = 2p+1 \neq \pm 1 \pmod{8}$ . These were discarded earlier for having $2$ as a generator; so we can immediately say that these will work in this case. $23$ , on the other hand, is of the form $q = 2p+1 \equiv \pm 1 \pmod{8}$ , so $23$ cannot have $2$ as a generator and is discarded here.

$3$ is easily checked as having $2$ as a generator, so the possible pairs $p,q$ are $(3, 7), (11, 23), (83, 167)$ . The sum of all such possible primes $p < 100$ is then $3 + 11 + 83 = \underline{97}$ .

First list all the Sophie German prime. Since 2 is a generator modulo prime $p$ , 2 is a quadratic non-residue of $p$ , thus $p$ is equal to 3 or 5 mod 8. Since 2 is not a generator modulo prime $q$ , the order of 2 modulo $q$ is some proper divisor of $q-1 = 2p$ , which is equal to 1, 2, or $p$ . One can readily discard 1 and 2 when $q > 3$ which happens to be true for all Sophie German primes. Hence $2^p$ is equal to 1 mod q, which means 2 is a quadratic residue mod q. Hence $2p+1 = q$ is equal to 1 or 7 mod 8. Combine with previous result, we can conclude that $p$ is equal to 3 mod 8 and $q$ is equal to 7 mod 8. We are left with 3 possible solutions of $p$ , which are 3, 11 and 83, and it is not hard to prove that they indeed satisfy all the problem conditions.

We recall the definition of Legendre symbol: $\left( \frac{a}{n} \right) \equiv a^{(n-1)/2} \pmod n$ which equals $1$ if $a$ is a quadratic residue mod $n$ , equals $-1$ if $a$ is not a quadratic residue mod $n$ , and equals $0$ if $a \equiv 0 \pmod n$ . (A number $a$ is a quadratic residue mod $n$ if there exists an integer $x$ such that $x^2 \equiv a \pmod n$ .) We also recall the second supplement to the law of quadratic reciprocity: for an odd prime $p$ , $\left( \frac{2}{p} \right) = (-1)^{(p^2-1)/8};$ that is to say, $2$ is a quadratic residue of $p$ if and only if $p \equiv \pm 1 \pmod 8$ . Next, we claim that if $2$ is a generator mod $p$ , then $2$ is not a quadratic residue mod $p$ . To see why, note that if $\left( \frac{2}{p} \right) = 2^{(p-1)/2} \equiv 1 \pmod p$ , then the multiplicative order of $2$ mod $p$ is strictly less than $p-1$ , so the powers of $2$ cannot generate all the nonzero residues of $p$ . It then follows that if $2$ is a generator mod $p$ , then $p \equiv \pm 3 \pmod 8$ .

Now that we have established this result, we can narrow down our candidates for $p$ . There are 24 odd primes less than 100 (we exclude $2$ because it is trivial to see it does not satisfy the given conditions): $\begin{aligned} \{ &3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, \\ &47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 \}. \end{aligned}$ Of these, only nine satisfy the condition that $q = 2p+1$ also be prime: $\{ 3, 5, 11, 23, 29, 41, 53, 83, 89 \}.$ Of these, only six satisfy $p \equiv \pm 3 \pmod 8$ : $\{ 3, 5, 11, 29, 53, 83 \}.$ And of these, only three satisfy $q = 2p+1 \not\equiv \pm 3 \pmod 8$ : $p \in \{ 3, 11, 83 \}.$ It is easy to check that $2$ is indeed a generator mod $p$ for the first two candidates. The third is more computational. We rely on the fact that the multiplicative order of $a$ mod $p$ must divide $\phi(p) = p-1$ , so that if the smallest positive $d \mid 82$ satisfying $2^d \equiv 1 \pmod {83}$ is $d = 82$ , then $2$ is a generator mod $83$ ; that is to say, we need only check those exponents that divide $82$ . We compute via repeated squaring $\begin{aligned} 2^2 &\equiv 4 \pmod {83}, \\ 2^4 &\equiv 4^2 \equiv 16 \pmod {83}, \\ 2^8 &\equiv 16^2 \equiv 7 \pmod {83}, \\ 2^{16} &\equiv 7^2 \equiv 49 \pmod {83}, \\ 2^{32} &\equiv 49^2 \equiv 77 \pmod {83}, \\ 2^{41} &= 2^{32} 2^{8} 2^1 \equiv 77(7)(2) \equiv 82 \pmod {83}, \\ 2^{82} &\equiv 82^2 \equiv 1 \pmod {83}. \end{aligned}$ Therefore, all three candidates satisfy the criteria, and the desired sum is $3 + 11 + 83 = 97.$

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199

Removing those over 99 or for which 2p+1 is not in the list leaves:

2, 3, 5, 11, 23, 29, 41, 53, 83, 89

Removing 2 and others for which the order of 2 mod p is not p-1 (that is 2^(p-1) is not the first power of 2 equal to 1) leaves:

3, 5, 11, 29, 53, 83

Removing those for which the order of 2 mod q is q-1 leaves:

3, 11, 83

The sum of these is 97.

Because $2$ is a generator modulo $p$ , $p$ is odd. Note that $q-1=2p,$ and $2^2=4 < q$ . The order of $2$ modulo $q$ is a divisor of $q-1$ , and $2$ is a generator if and only if the order is $q-1$ . So the only way $2$ would be not a generator modulo $q$ is if $2^p\equiv 1 \pmod{q}$ . As such, $\left( 2^{ \frac{p+1} {2} }\right) ^2 \equiv 2 \pmod{q}$ .

This implies that $2$ is a quadratic residue modulo $q$ , which happens if and only if $q$ is congruent to $1$ or $7$ modulo $8$ . Also, $2$ cannot be a quadratic residue modulo $p$ , so $p$ is congruent to $3$ or $5$ mod $8$ . With $q=2p+1$ , this means that $p\equiv 3 \pmod 8$ . Also, because $p$ and $2p+1$ are both primes, either $p=3$ or $p\equiv 2\pmod 3$ . By the Chinese Remainder Theorem, either $p=3$ or $p\equiv 11 \mod {24}$ .

If $p=3$ , then $q=7$ is prime. Checking the primality condition for $p$ and $2p+1$ with $p\equiv 11 \pmod {24}$ and $p<100$ . we get primes $p=11$ and $p=83$ .
For $p=3$ and $q=7$ the conditions are easy to check.
For $p=11$ and $q=23$ we know from the discussion above that $2$ is not a generator modulo $23$ . Modulo $11$ , one can check directly that $2$ is a generator, or use the same argument, since $2$ is not a quadratic residue and $p-1=2\cdot 5$ with $5$ prime.
Similarly, for $p=83$ and $q=167$ , we know that $2$ is a quadratic residue modulo $q$ and not a quadratic residue modulo $p$ . Because $p-1=2\cdot 41$ and $41$ is prime, this implies that $p=83$ also works.

Therefore, the answer is $3+11+83=97.$

I just brute forced this in Mathematica. I don't normally do that at all, but I couldn't see a handle on any other way...

Let $S$ denote the set of all primes less than $200$ . Then, we will start by listing all primes $p\in S$ such that $p>99$ or such that $2p+1\notin S$ . These are $${2,3,5,11,23,29,41,53,83,89}.$$ Now, we can remove $2$ and remaining $p$ such that $\operatorname{ord}_p(2)\neq p-1.$ This leaves $${3,5,11,29,53,83}.$$ Moreover, we can remove all $p$ such that $\operatorname{ord}_{2p+1}(2)=2p$ . The remaining primes are then $\{3,11,83\}$ so the desired sum is $3+11+83=\boxed{97}$