Prime Pickle

Claim If $a,b,c,n$ are four natural numbers such that $a^b \equiv a^c \equiv 1 \pmod{n}$ , then $a^{\gcd(b,c)} \equiv 1 \pmod{n}$ .

Proof Let $G= \gcd(b,c)$ . By Bezouts's lemma, we can find two integers $u$ and $v$ such that $bu+cv= G$ . Then, note that $a^G \equiv a^{bu+cv} \equiv \left ( a^b \right ) ^u \times \left ( b^c \right ) ^v \equiv 1 \pmod{n}$ This proves our desired result. QED
$$
Claim If $p$ is a prime and $q$ is a prime divisor of $p-1$ , then we can find a positive integer $a \not \equiv 1 \pmod{p}$ such that $a^q \equiv 1 \pmod{p}$ .

Proof Let $f(x)= x^{\frac{p-1}{q}}-1$ . Consider the residues of $f(x) \pmod{p}$ . Since the degree of $f(x)$ is $\dfrac{p-1}{q}$ , it can have at most $\dfrac{p-1}{q}$ roots. Again, note that $\dfrac{p-1}{q} < p-1$ . Then, there must exist an integer $r$ such that $p \not \mid r$ , and $r^{\frac{p-1}{q}} \not \equiv 1 \pmod{p}$ . Take $a= r^{\frac{p-1}{q}}$ . Then, note that $a^q \equiv r^{p-1} \equiv 1 \pmod{p}$ where the last step follows from Fermat's little theorem. This proves our desired result. QED $$ $$ We now go back to the main problem. Note that $(a^2-a)(b^2-b)= ab(a-1)(b-1)$ Then, $(a^2-a)(b^2-b) \not \equiv 0 \pmod{p}$ simply means $p$ divides neither of $a, b, a-1, b-1$ . Since $p \not \mid a$ , $\gcd (p, a)= 1$ . The first congruence yields: $a^{n-m} \equiv 1 \pmod{p}$ Note that $b^{n-m} \equiv \left ( a^m \right ) ^{n-m} \equiv \left ( a^{n-m} \right ) ^{m} \equiv 1 \pmod{p}$ Note that $b^{n}= b^{n-m} \times b^m$ . The second congruence yields: $b^{n-m} \times b^m \equiv a \pmod{p}$ $\implies 1 \times \left ( a^m \right ) ^m \equiv a \pmod{p}$ $\implies a^{m^2} \equiv a \pmod{p}$ Again, since $\gcd (a, p)= 1$ , we can divide both sides by $a$ to obtain: $a^{m^2-1} \equiv 1 \pmod{p}$ Now, note that if $\gcd (n-m, m^2-1)= 1$ , the first claim alongside the congruencies $a^{n-m} \equiv 1 \pmod{p}$ and $a^{m^2-1} \equiv 1 \pmod{p}$ yields: $a^1 \equiv 1 \pmod{p}$ This is a contradiction, since the third condition states that $p \not \mid a-1$ .
$$ So far, we have been able to prove that a necessary condition for the existence of such a $(a,b)$ is $\gcd (n-m, m^2-1) > 1$ . We shall now prove that this is the sufficient condition.

Let $q$ be a prime divisor of $m^2-1$ . Dirichlet's theorem states that there exists a prime $p$ such that $q \mid p-1$ . From the second claim, we can find a positive integer $a$ such that $a \not \equiv 1 \pmod{p}$ and $a^q \equiv 1 \pmod{p}$ . Take $b= a^m$ . Note that if $q \mid m-1$ , $b \equiv a^m \equiv a^{m-1} \times a \equiv \left ( a^{q} \right ) ^{\frac{m-1}{q}} \times a \equiv a \pmod{p}$ Again, if $q \mid m+1$ , we have: $b \equiv a^m \equiv \frac{a^{m+1}}{a} \equiv \frac{\left ( a^q \right ) ^\frac{m+1}{q}}{a} \equiv \frac{1}{a} \pmod{p}$ It is now obvious that $a$ and $b$ satisfy the mentioned conditions.

$$ Conclusion
For each $m$ , the number $n$ satisfies the mentioned conditions iff $m^2-1$ and $m-n$ share a common prime factor. $$ We then have to find the number of positive integers $m \leq 100$ such that there are strictly more than $499$ values of $n$ such that $m-n$ and $m^2-1$ share a common prime factor.
$$ Case $1$ : $m \equiv 1 \pmod{2}$
Then, note that $2 \mid m^2 - 1$ . Take any odd $n$ . Then, note that $2 \mid m-n$ . So, for any odd $n$ , the conditions will be satisfied. Since there are $500$ odd integers from $1$ to $100$ , each odd choice of $m$ will count in atleast $500$ solutions for $n$ . Since there are $50$ even integers from $1$ to $100$ , this case produces $50$ solutions.

Case $2$ : $m \equiv 0 \pmod{2}$
Then, note that $2 \nmid m^2 - 1$ . Let $q_1$ , $q_2$ , $\cdots$ , $q_k$ be the odd prime divisors of $m^2-1$ .First, note that for all $q_i$ , the number of multiples of $q_i$ in the range $[1, 1000]$ is given by $\left \lfloor \frac{1000}{q_i} \right \rfloor \leq \frac{1000}{q_i}$

The number of positive integers $\leq 1000$ divisible by $q_1q_2\cdots q_k$ is less than $\sum \limits_{i=1}^{k} \left \lfloor \frac{1000}{q_i} \right \rfloor \leq 1000 \times \left ( \sum \limits_{i=1}^{k} \frac{1}{q_i} \right )$

It then follows that if $\sum \limits_{i=1}^{k} \frac{1}{q_i} < \frac{1}{2}$ , then the number of solutions for $n<1000$ will be $<500$ .

Now, suppose $2, 3$ and some other prime $\geq 37$ is in the set $\{q_1, q_2, \cdots , q_k \}$ . The number of multiples of either $2$ or $3$ in the range $[1, 1000]$ is given by (by PIE): $\left \lfloor \frac{1000}{2} \right \rfloor + \left \lfloor \frac{1000}{3} \right \rfloor - \left \lfloor \frac{1000}{15} \right \rfloor = 467$ Since the other prime is $\geq 37$ , the largest number of multiples it can have in the range $[1, 1000]$ is $\left \lfloor \frac{1000}{37} \right \rfloor = 30$ Note that $467+30= 497 < 500$ . This shows that if $2, 3$ , and some other prime $\geq 37$ is in the prime factorization of $m^2-1$ , the number of solutions for $n$ will be strictly less than $500$ .

Since we are considering only even $m$ , we can let $m=2k$ , where $k$ ranges through all integers from $1$ to $50$ . From the first two observations, we can rule out all $k$ except $6, 9, 17, 28, 32, 38, 43, 47$ . We can now manually go through these $7$ numbers. However, note that the number of multiples of either $3$ , $5$ , or $7$ is given by : $\left \lfloor \frac{1000}{3} \right \rfloor + \left \lfloor \frac{1000}{5} \right \rfloor + \left \lfloor \frac{1000}{7} \right \rfloor - \left \lfloor \frac{1000}{15} \right \rfloor - \left \lfloor \frac{1000}{35} \right \rfloor - \left \lfloor \frac{1000}{21} \right \rfloor + \left \lfloor \frac{1000}{21} \right \rfloor= 543 > 500$ This shows that $k= 17, 32$ , and $38$ works. We similarly calculate the number of multiples for the remaining four possibilities of $k$ . Doing this, we can show that it is greater than $500$ for $k= 6, 28$ and $43$ , but $<500$ for $47$ and $9$ . Thus, this case produces $3+3= 6$ solutions in all.
$$ Summing them up, the total number of possibilities for $m$ is $50+6= \boxed{56}$ .

The conditions imply that $a^{mn-1}$ and $a^{m-n}$ are both congruent to $1$ mod $p$ . Let $x$ be the order of $a$ mod $p$ . So $x$ divides gcd $(mn-1,m-n)$ . Note that this equals gcd $(m^2-1,m-n)$ . Conversely, if gcd $(m^2-1,m-n) = x > 1$ , we can find $p,a,b$ satisfying the conditions; just take $p \equiv 1$ mod $x$ and let $a$ be an element of multiplicative order $x$ , and $b \equiv a^m$ .

So we must find all values of $m$ such that the size of the set $\{ n \in {\mathbb Z} : 1 \le n \le 1000, {\rm gcd}(m^2-1,m-n) > 1 \}$ is at least 500.

If $m$ is odd, then this set is always big enough since all odd $n$ are in it. If $m$ is even, then a computer search seems to be the easiest way to proceed; I get $\{ 14, 34, 56, 64, 76, 86, 94 \}$ as the admissible even values. So the total number is $\fbox{57}$ .