# Finding consecutive naturals that all fail to have inverses modulo $70$

I'm not sure how to prove the following statement true or false.

There exist five consecutive naturals that all fail to have inverses modulo $70$.

I know I can apply the Euclidean algorithm to find the inverse modulo $70$ of some number, but I'm not sure how to apply the algorithm to this problem.

• Hint. Look for consecutive numbers each of which shares a factor with $70$. (You're right to note that the Euclidean algorithm helps find inverses one at a time when they exist, but doesn't help here.) Commented Mar 6, 2017 at 14:05
• @Peter Thanks, I think the chinese remainder theorem is what I'm supposed to use for this problem. Commented Mar 6, 2017 at 14:12
• Proof that there are no $6$ consecutive numbers $n$ with $gcd(n,70)\ne 1$ : Of $6$ consecutive numbers, exactly $3$ are even. Of the remaining $3$ numbers, at most one is divisble by $5$ and at most one is divisble by $7$. So, there must be at least one number coprime to $70$. Commented Mar 6, 2017 at 14:14
• The following numbers upto $1000$ are possible starting numbers of the sequence : 4 62 74 132 144 202 214 272 284 342 354 412 424 482 494 552 564 622 634 692 704 762 774 832 844 902 914 972 984 Commented Mar 6, 2017 at 14:20

Any number that is coprime to a modulus will have an inverse, so we need to find $5$ consecutive numbers that share a factor with $70$.

$70$ has three primes factors: $2,5,7$. Of any $5$ consecutive numbers, two or three will be even, but at most one will be divisible by $5$ or $7$. So we need three even numbers with an odd multiple of $5$ and an odd multiple of $7$ in the second and fourth positions. Since odd multiples of $5$ are all $\equiv 5\bmod 10$, it's apparent this means we need to look for cases where $7k \equiv \{3,7\} \bmod 10$. There are two such cases below $70$: $k=1$ and $k=9$ (giving $7$ and $63$), with the two options of $5$ consecutive numbers:

$$\{4,5,6,7,8\} \text{ and } \{62,63,64,65,66\}$$

For those comfortable with negative values in modular arithmetic, the second set is the negation of the first, that is, $\{62,63,64,65,66\} \equiv \{-8,-7,-6,-5,-4\} \bmod {70}$ .

• $\{62,63,64,65,66\} \equiv \{-8,-7,-6,-5,-4\} \pmod {70}$, which is not a surprise Commented Mar 6, 2017 at 14:17
• @Joffan: This is probably somehting trivial, but I do not see it: why do we need to look for cases where $7k \equiv \{3,7\} \mod 10$ and why do your sets follow from $k = 1$ or $k = 9$? Commented Mar 6, 2017 at 14:49
• @Joffan: really my bad: I was not sure how we could find from $k = 1$ what consecutive numbers to take, but since we need the odd multiple of $5$, this means that we already have $5$ and $7$ and this determines also the even numbers. Absolutely my bad. Thank you for the clarification! Commented Mar 6, 2017 at 15:03
• @Joffan: really really sorry for all the bothering, but how do you know that $7k$ has to be congruent with $3$ or $7$ and for example not with $1$ or $9$? Commented Mar 6, 2017 at 15:47
• It needs to be $2$ different from the multiple of $5$ to fit in the sequence. Commented Mar 6, 2017 at 15:48

Note that $x \in \mathbb{N}$ has an inverse modulo $n$ if and only if $\text{gcd}(x,n) = 1$. Looking for the prime decomposition of $70$, we see that $$70 = 2 \cdot 5 \cdot 7.$$ Now clearly $4, 5, 6, 7, 8$ don't have greatest common divisor $1$ with $70$ and therefore no inverse modulo $70$.

The numbers $[4,5,6,7,8]$ satisfy the required property.