Reverse of Chinese Remainder Theorem

1.3k Views Asked by At

For the following:

$(102n-51) \not\equiv 2 \pmod {2,3,5,7,11,13,...,\sqrt{102n-51}}$

(That's probably completely incorrect use of symbols, but I mean not equivalent to 2 mod any prime less than $\sqrt{102n-51}$)

here are my questions:

  1. What is the first (smallest) $n$ solution?
  2. Are there infinitely many $n$ solutions?
  3. (Most importantly) Is there a way we'd know (be able to prove) there must exist an $n$ solution where $n$ is less than a certain value?

If anything here is unclear, please ask. Also, please feel free to suggest edits to the question (or title) that might make this make more sense, or add pertaining tags. I'm having a hard time classifying this question and even expressing it clearly, but feel it has a lot of value.

EDIT: Thanks for the answers! I still have yet to receive an answer to question 3, of which I had the most interest. As well, I'd like to take things a step further. How about $102n-51$ simultaneously

$\not\equiv 2 \pmod {2,3,5,7,11,13,...,\sqrt{102n-51}}$

and

$\not\equiv 4 \pmod {2,3,5,7,11,13,...,\sqrt{102n-51}}$

2

There are 2 best solutions below

3
On

HINT: $$(102n - 51) \not\equiv 2 \pmod p$$ For every prime $0<p<\sqrt{102n-51}$. This means that $102n-53$ has no prime factors smaller than $\sqrt{120n-51}$. It also means that $102n-53$ has no prime factors greater than: $$\dfrac{102n-53}{\sqrt{102n-51}}$$which for larger $n$ basically means that $\lceil\sqrt{102n-51}{}\rceil$ is both prime and the only prime factor of $102n-53$

3
On

Number $n$ is prime iff it's not divisible by any prime $p \leq \sqrt{n}$.

In your case you are looking for $102n-53$ not being divisible by any prime $p \leq \sqrt{102n-51}$. We can reduce it to $p \leq \sqrt{102n-53} < \sqrt{102n-51}$.

E.g. $n=2$ gives $151$ which is prime.

And yes, there are infinitely many such primes, you can re-write $102n-53=102(n-1)+49$ and apply Dirichlet's theorem on arithmetic progressions because $102$ and $49$ are coprime.

And I believe you can apply Prime number theorem for arithmetic progressions to estimate $n$.