Why is the list $1+N,1+2N, \dots, 1+(n+1)N$ relatively prime?

Question

I was reading:

Take $N \in \mathbf N$ such that $a_i \leq N$ for all $i \leq n$ and N is a multiple of every prime number ≤ n. We claim that then 1 + N, 1 + 2N, . . . , 1 + nN, 1 + (n + 1)N are pairwise relatively prime. To see this, suppose p is a prime number such that p | 1+iN and p | 1+jN (1 ≤ i < j ≤ n+ 1); then p divides their difference (j − i)N, but p ≡ 1 mod N, so p does not divide N, hence p | j − i ≤ n. But all prime numbers ≤ n divide N, and we have a contradiction

however, it didn't really make sense to me.

My confusion is where:

$$p \equiv 1 \pmod N$$

came from and how it contributed to the proof. Why does it matter that that if $p \equiv 1 \mod N$ is true then $p$ doesn't divide $N$?

I feel this suppose to be a pretty elementary proof but it is escaping me. What is the simplest way to see this proof? Or what step is the proof skipping? I know this suppose to be easy but something is escaping me....

---

context:

https://faculty.math.illinois.edu/~vddries/main.pdf

Answer 1

All you need is the conclusion that $p$ does not divide $N.$ It is enough to show that $\gcd(p,N) = 1.$ Now, as there is an integer $t$ such that $pt = 1 + jN,$ we arrive at the Bezout expression $$ pt - jN = 1 $$ which does the trick. See how, if $p|N,$ Bezout would force $p|1.$

Meanwhile, $N$ is divisible by all primes up to little $n.$ Since $p$ does not divide $N,$ we find that $$ p > n \; . $$ This leads to a contradiction when $p |(j-i) \leq n$

I do not see any reason to conclude that $p \equiv 1 \pmod N.$ That sort of thing happens when $N$ divides something involving $p,$ not when $p $ divides something involving $N.$

Answer 2

We want to show:

$$ 1+N, 1+2N, \dots, 1+(n+1)N$$

is coprime (i.e. share no common factors). It's sufficient to show they don't share a common prime factor (since all other factors are made of primes, since if its a factor of a specific number then that number can be turned to primes and those divide the number in question. So if the building blocks don't divide the number no other number does either).

Consider any pair $1 + iN,1+jN$ ($0 \leq i,j \leq n+1)$ and any prime $p$ less than either number in the pair. For the sake of contradiction suppose $p | 1+iN$ and $p | 1+Nj$. This means $1+Nj = p t_j$ and $1+Ni = p t_i$. We also have $p$ divides the difference:

$$ p | N (i-j) $$

so $p|N$ or $p|i-j$ (since $p$ is prime i.e. "atomic"). Notice from earlier facts that $1 = Nj - p t_j $ is true so if $p|N$ we'd get that $p$ divides $1$ which is absurd because $p$ is prime. So $p \not \mid N$. So $p | i - j$. Notice that $i,j$ are between 1 to n so their difference is less that $n$. So $p | i - j \leq n$ which means $p$ must be less than $n$. But that can't be true either because $N$ is a multiple of all primes less than $n$ and if $p \leq n$ and is prime, then it must divide $N$. So contradicts an earlier fact we derived. Thus, this sequence must be coprime $ 1+N, 1+2N, \dots, 1+(n+1)N$ (share no common factors, especially a prime factor which is what we showed explicitly).