# 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.) – Ethan Bolker Mar 6 '17 at 14:05
• @Peter Thanks, I think the chinese remainder theorem is what I'm supposed to use for this problem. – cdignam Mar 6 '17 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$. – Peter Mar 6 '17 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 – Peter Mar 6 '17 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 – Henry Mar 6 '17 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$? – Student Mar 6 '17 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! – Student Mar 6 '17 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$? – Student Mar 6 '17 at 15:47
• It needs to be $2$ different from the multiple of $5$ to fit in the sequence. – Joffan Mar 6 '17 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.