1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Are two integers coprime if they are coprime mod(n)?

  1. Aug 10, 2016 #1
    1. The problem statement, all variables and given/known data
    Show that out of a set of ten consecutive integers, at least one is coprime to all of the others.

    2. Relevant equations
    Lemma: Out of a set of n consecutive integers, exactly one is divisible by n. (Given).

    3. The attempt at a solution
    Let a1, a2...a10 be consecutive integers. Let a11(mod10), a2≡ 2(mod10)...a100(mod10).

    Observe that 7 is coprime to the other integers from 1 to 10. Does this mean that 7(mod10) is coprime to the other integers in ℤ10, and if so, does this mean that a7 is coprime to the other ai?

    Also, sorry that I've been throwing so many questions on here in the last few weeks. Thank you all for being so patient :)
  2. jcsd
  3. Aug 10, 2016 #2
    Never mind, 7 has a multiplicative inverse, 3, in the integers modulo 10, so it can divide the other elements.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted