June 29th Potd Proof

July 29th 2007 POTD Proof Problem by: Landen Created for: #Math on EFNet IRC Network Author: InfiniteI 10 July 2007

Problem: Show that the rational number 12m + 1 30m + 2 is in lowest terms for any positive integer m. Lemma. If 12m + 1 is even then m is not a positive integer. Proof. Assume that m is a positive integer. We proceed by cases, according to whether m is even or odd. Case 1. Let m be a positive even integer. Then m = 2a, where a ∈ Z and a > 0. Observe that 12m + 1

=

12(2a) + 1

=

2(12a) + 1.

Since 12a is an integer, 12m + 1 is odd. Case 2. Let m be a positive odd integer. Then m = 2b + 1, where b ∈ Z and b ≥ 0. Observe that 12m + 1

=

12(2b + 1) + 1

=

24b + 13

=

2(12b + 6) + 1.

Since 12b + 6 is an integer, 12m + 1 is odd. Proof of Main Result. Assume, to the contrary, that the rational number 12m + 1 30m + 2 is not in lowest terms for any positive integer m. In other words, 12m + 1 is divisible by 30m + 2.

1

That is, 30m + 2 | 12m + 1. Thus, 12m + 1 = n(30m + 2), where n ∈ Z and n 6= 0. We proceed by cases, according to whether m is a positive even integer or positive odd integer. Case 1. Let m be a positive even integer. Then m = 2k, where k ∈ Z and k > 0. It follows that 12m + 1

=

n(30m + 2)

= n[30(2k) + 2] = n(60k + 2) =

2(30kn + n).

Since 30kn + n is an integer, 12m + 1 is even. By the Lemma, if 12m + 1 is even, then m is not an integer. Therefore, we have a contradiction. Case 2. Let m be a positive odd integer. Then m = 2l + 1, where l ∈ Z and l ≥ 0. Observe that 12m + 1

=

n(30m + 2)

= n[30(2l + 1) + 2] = n(60l + 32) =

2(30ln + 16n).

Since 30ln + 16n is an integer, 12m + 1 is even. By the Lemma, if 12m + 1 is even, then m is not an integer. Therefore, we have a contradiction.

2