12
$\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$
  • 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$ – Ethan Bolker Mar 6 '17 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 Mar 6 '17 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 Mar 6 '17 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 Mar 6 '17 at 14:20
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$
  • 7
    $\begingroup$ $\{62,63,64,65,66\} \equiv \{-8,-7,-6,-5,-4\} \pmod {70}$, which is not a surprise $\endgroup$ – Henry Mar 6 '17 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 Mar 6 '17 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 Mar 6 '17 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 Mar 6 '17 at 15:47
  • 2
    $\begingroup$ It needs to be $2$ different from the multiple of $5$ to fit in the sequence. $\endgroup$ – Joffan Mar 6 '17 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.