43, 47, 48, 49, 50, 51, 52, 53, 57, 59, 61, 64, 67, 69, 71, 73, 77, 79, 80, 81, 83, 87, 89, 91, 93, 95, 97, 98, 99, 100, 101, 102.

3.6

# Factor the Divisor

Our final trick is not really a divisibility test itself, but is a way to combine other divisibility tricks. For example, to test if a number is divisible by 6, we can check to see if it is divisible by both 2 and 3. A number is divisible by 56, if and only if it is divisible by both 7 and 8.

d

factors

d

factors

d

factors

d

factors

d

factors

6

23

33

3 11

51

3 17

69

3 23

87

3 29

10

25

34

2 17

52

4 13

70

257

88

8 11

12

43

35

57

54

2 27

72

89

90

295

14

27

36

49

55

5 11

74

2 37

91

7 13

15

35

38

2 19

56

87

75

3 25

92

4 23

18

29

39

3 13

57

3 19

76

4 19

93

3 31

20

45

40

85

58

2 29

77

7 11

94

2 47

21

37

42

237

60

435

78

2 3 13

95

5 19

22

2 11

44

4 11

62

2 31

80

16 5

96

32 3

24

83

45

95

63

97

82

2 41

98

2 49

26

2 13

46

2 23

65

5 13

84

437

99

9 11

28

47

48

16 3

66

2 3 11

85

5 17

100

4 25

30

235

50

2 25

68

4 17

86

2 43

102

2 3 17

If 1 is the greatest common divisor of m and n, we say that m and n are rel tively prime. Observe that 6 = 2 · 3 and 2 and 3 are relatively prime; also, 56 = 7 · 8 where 7 and 8 are relatively prime.

Factor the Divisor Trick: Suppose that d = mn where m and n are relatively prime. Then d divides a number a if and only if m divides a and n divides a.

We list below all the d (2 ≤ d ≤ 102) that can be written as the product of numbers that are (pairwise) relatively prime.

13