gcd(a,b,c)=1
Overall coprime
There is no prime factor shared by all the numbers at once.
gcd(6,10,15)=1
Yet gcd(6,10)=2, gcd(6,15)=3, and gcd(10,15)=5. No pair is coprime.
Build Pairwise-Coprime Groups and Test Mixed Constraints
两两互质分组；整体最大公约数与每一对最大公约数
Learn the difference between an entire set having GCD 1 and every pair being coprime. Turn shared factors into a conflict map, prove a lower bound on the number of groups, construct an optimal grouping, and validate flexible mixed-condition examples.
One GCD describes the whole set. Pairwise coprime means every single pair passes.
Answers autosave in this browser.
Mission 1
Not completeSeparate one overall GCD from all pairwise GCDs
These two ideas sound similar, but they answer different questions. A set can have overall GCD 1 even when no pair is coprime.
gcd(each pair)=1
Pairwise coprime
Every pair chosen from the set has greatest common divisor 1.
4, 9, 25 are pairwise coprime
All three numbers are composite, showing that “pairwise coprime” does not mean “prime.”
Meaning checkpoint
Need a hint? Start here
Check all three pairs separately from the overall GCD.
Check why it works
6,10,15 share no common prime across all three, yet every pair shares a prime. 1; no; yes; zero coprime pairs.
Mission 2
Not completeBuild a pairwise GCD matrix
A matrix is a table with the same input list labeling its rows and columns. Each off-diagonal cell shows the GCD of its row and column entries. A dash means an entry paired with itself; do not count it. Each unordered pair appears twice, so count only one side of the diagonal. A green cell means GCD 1; a red cell marks a shared-factor conflict.
Action
original-set matrix checkpoint
Use the fixed eight numbers 26,33,34,35,63,85,91,143, even if you change the matrix inputs.
Need a hint? Start here
Count each unordered pair once, not both mirrored matrix cells.
Check why it works
Eight entries make 8×7/2=28 unordered pairs. Ignore the diagonal and count each mirrored pair once. Overall GCD 1; 11 conflicting pairs; not pairwise coprime; 28 total pairs.
Mission 3
Not completeRead the worked example numbers as prime-factor cards
Guided Practice 6 asks us to split eight numbers so that any two in the same group have GCD 1. First identify exactly which pairs cannot stay together.
How to read the map
Each number is a node. Select a factor card to highlight that number and its direct conflict neighbors; the highlighted neighbors need not conflict with each other. A group with one member is valid because it contains no conflicting pair. A red connection joins two numbers whose GCD is greater than 1. Connected nodes must be placed in different groups.
No edge between two nodes: that pair may share a groupEdge: must separate
This map records 11 conflicting pairs. It does not yet tell us the minimum number of groups.
Factor-conflict checkpoint
Need a hint? Start here
An edge means a shared factor greater than 1: these numbers must be separated.
Check why it works
35 shares 7 with 63 and 91, and 5 with 85. Do not count 35 itself. 13; 17; 11; three other cards conflict with 35.
Mission 4
Not completeProve that at least three groups are necessary
A construction alone proves that a certain number of groups is enough. To prove a minimum, we also need a lower bound.
A three-way conflict
26gcd 1391gcd 13143
Each pair among these three numbers has a common factor of 13. Therefore no two may share one pairwise-coprime group.
Lower-bound conclusion
3 mutually conflicting numbers ⇒ at least 3 groups
Two groups cannot hold three objects when every pair must be separated. This proves a lower bound of three.
We still need a valid three-group construction to prove that three is attainable.
Lower-bound checkpoint
Need a hint? Start here
Three mutually conflicting numbers require three different groups.
Check why it works
Every two must be separated, so two groups cannot suffice. Common factor greater than 1: 13; lower bound 3; add a valid construction; no,26 and143 cannot share a group.
Mission 5
Not completeBuild an optimal three-group construction
Assign every original number once to Group A, B, or C. All three groups must be nonempty, but their sizes need not be equal. The validator accepts any grouping in which every pair inside each group has GCD 1.
Need a hint? Start here
Use every original number once and inspect each pair inside each group.
Check why it works
Group sizes may differ, and all three groups must be used. One valid construction: {26,35}, {33,34,91}, {63,85,143}. Together with the lower bound, this proves the minimum is 3.
Mission 6
Not completeEnumerate every optimal grouping
The worked example asks only for the minimum number of groups. A complete search is useful added scaffolding: it confirms that three groups work in several different ways.
Unlabeled means names do not matter. If Group A and Group B exchange names but keep the same members, the partition has not changed. Count the membership arrangement once.
Condition-based search
The search uses the worked example order and creates unlabeled groups canonically, so swapping the names A, B, and C does not create a new answer.
Enumeration checkpoint
Need a hint? Start here
Swapping group names does not create a new partition.
Check why it works
The complete search uses a fixed order to avoid counting relabelings twice. Minimum 3; seven unlabeled optimal groupings; original model passes; the grouping is not unique.
Mission 7
Not completeUse a general minimum-group laboratory
Enter up to ten distinct positive integers. The laboratory builds the conflict graph and finds the smallest number of pairwise-coprime groups by complete backtracking.
Use 2–10 distinct positive integers, each no greater than 1,000,000.
Action
Laboratory checkpoint
Need a hint? Start here
Find a conflict lower bound and a grouping that meets it.
Check why it works
For 6,10,15,21 use {6},{10,21},{15}; 10 and21 are coprime. Minimums: 1; 3; 3; 1.
Mission 8
Not completeConstruct triples under mixed coprime constraints
These are the two construction exercises from the worked example. We use positive whole numbers in both panels and preserve the worked example bounds. Repeated values are allowed; count pairs of positions: first–second, first–third, and second–third. Repeated entries still occupy different positions. Complete and audit both panels to finish the mission.
Exercise 8: exactly two coprime pairs
Enter three positive whole numbers less than 10 so that exactly two of the three pairs are coprime.
Exercise 11: overall GCD 1, but no coprime pair
Enter three positive whole numbers less than 20 whose overall GCD is 1 while every pair has GCD greater than 1.
Need a hint? Start here
Check the size restriction, the overall GCD and each pair. Both panels must pass.
Check why it works
First panel may use 2,2,3, with exactly two coprime pairs. Second may use 6,10,15. For 2,2,3 the pair GCDs are 2,1,1. For 6,10,15 they are 2,3,5 and the overall GCD is 1. All size bounds hold.
Mission 9
Not completePairwise-coprime grouping workshop
Correct all eight questions to complete the workshop.
0 / 8
Need a hint? Start here
Choose the method before calculating. Revisit the local hint for that method, then verify every condition in the question.
Check why it works
Use each unordered pair once. Answers: 1; 0; 2; 3; 13; 17; yes; 7.
Mission 10
Not completeExit ticket
Complete all ten missions and answer all five exit items correctly to earn your certificate.
0 / 5
GCD
Pairwise-Coprime Grouping Architect
This certifies that a determined mathematician can distinguish overall from pairwise coprimality, map shared-factor conflicts, prove minimum group counts, and construct valid groupings under mixed GCD conditions.
Lesson 19.6 • Chapter 19
Optional reflection — not automatically graded
Need a hint? Start here
Choose the method before calculating. Revisit the local hint for that method, then verify every condition in the question.
Check why it works
14,21,35 conflict pairwise, so each needs a different group. Answers: 1; 3; 2; 2; 3.
Learning notes and instructional additions
The original asks students to split 26, 33, 34, 35, 63, 85, 91, and 143 into the fewest groups so that any two numbers in one group have GCD 1.The conflict graph, pairwise GCD matrix, complete enumeration of seven unlabeled optimal original groupings, general minimum-group solver, and flexible validators are added instructional scaffolds.The application does not add an unstated distinctness condition to Exercise 8.