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

  • Thread starter jack476
  • Start date
  • Tags
    Integers
In summary, the problem is to show that out of a set of ten consecutive integers, at least one is coprime to all of the others. The given lemma states that exactly one integer in a set of n consecutive integers is divisible by n. The attempt at a solution considers the case of a set of integers modulo 10, where 7 is coprime to the other integers. However, it is later determined that 7 has a multiplicative inverse in this set, making it not coprime to all elements.
  • #1
jack476
328
125

Homework Statement


Show that out of a set of ten consecutive integers, at least one is coprime to all of the others.

Homework Equations


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

The Attempt at a Solution


Let a1, a2...a10 be consecutive integers. Let a1≡1(mod10), a2≡ 2(mod10)...a10≡0(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 :)
 
Physics news on Phys.org
  • #2
Never mind, 7 has a multiplicative inverse, 3, in the integers modulo 10, so it can divide the other elements.
 

Related to Are two integers coprime if they are coprime mod(n)?

1. What does it mean for two integers to be coprime?

Two integers are coprime if they do not have any common factors other than 1. In other words, their greatest common divisor (GCD) is 1.

2. How do you determine if two integers are coprime?

To determine if two integers are coprime, you can calculate their GCD using a method such as Euclid's algorithm. If the GCD is 1, then the integers are coprime.

3. What does it mean for two integers to be coprime mod(n)?

Two integers are coprime mod(n) if their remainders when divided by n are coprime. In other words, their GCD when divided by n is also 1.

4. How is coprimality mod(n) different from regular coprimality?

Regular coprimality refers to the GCD of two integers, while coprimality mod(n) refers to the GCD of the remainders when the integers are divided by n. In some cases, two integers may be coprime, but not coprime mod(n).

5. Can two integers be coprime if they are not coprime mod(n)?

Yes, it is possible for two integers to be coprime but not coprime mod(n). This can happen if their GCD is a multiple of n, but not exactly equal to n. For example, 6 and 15 are coprime, but not coprime mod(7) since their GCD is 3, which is a multiple of 7.

Similar threads

B Calculating the coprime probability of two integers in a different way
    • General Math
Replies
13
Views
1K
Number theory: gcd(a,b)=1 => for any n, gcd(a+bk,n)=1 for some k
    • Calculus and Beyond Homework Help
Replies
1
Views
2K
Proof that Algebraic Integers Form a Subring
    • Calculus and Beyond Homework Help
Replies
1
Views
2K
Congruence and Primes: Proving the Order of an Integer Modulo a Prime
    • Calculus and Beyond Homework Help
Replies
4
Views
975
MHB P-1 consecutive numbers coprime to n
    • General Math
Replies
1
Views
3K
Partition of Integers with mod
    • Calculus and Beyond Homework Help
Replies
4
Views
2K
U(n) as an External Direct Product
    • Calculus and Beyond Homework Help
Replies
11
Views
1K
MHB Resurrecting a previous post. Coprime mod n implies coprime-ish mod n.
    • General Math
Replies
2
Views
2K
Using a Problem Solving Technique for a simple word problem
    • STEM Educators and Teaching
Replies
24
Views
2K
Showing a property of Abelian groups of order n
    • Calculus and Beyond Homework Help
Replies
4
Views
1K

Hot Threads

Recent Insights

Back
Top