11
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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.) $\endgroup$ Commented Mar 6, 2017 at 14:05
  • 1
    $\begingroup$ @Peter Thanks, I think the chinese remainder theorem is what I'm supposed to use for this problem. $\endgroup$
    – cdignam
    Commented Mar 6, 2017 at 14:12
  • 6
    $\begingroup$ 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$. $\endgroup$
    – Peter
    Commented Mar 6, 2017 at 14:14
  • 1
    $\begingroup$ 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 $\endgroup$
    – Peter
    Commented Mar 6, 2017 at 14:20

3 Answers 3

17
$\begingroup$

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}$ .

$\endgroup$
6
  • 7
    $\begingroup$ $\{62,63,64,65,66\} \equiv \{-8,-7,-6,-5,-4\} \pmod {70}$, which is not a surprise $\endgroup$
    – Henry
    Commented Mar 6, 2017 at 14:17
  • 1
    $\begingroup$ @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$? $\endgroup$
    – Student
    Commented Mar 6, 2017 at 14:49
  • 1
    $\begingroup$ @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! $\endgroup$
    – Student
    Commented Mar 6, 2017 at 15:03
  • 1
    $\begingroup$ @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$? $\endgroup$
    – Student
    Commented Mar 6, 2017 at 15:47
  • 2
    $\begingroup$ It needs to be $2$ different from the multiple of $5$ to fit in the sequence. $\endgroup$
    – Joffan
    Commented Mar 6, 2017 at 15:48
6
$\begingroup$

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$.

$\endgroup$
4
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .