12-Hour Clock Arithmatic

ss_yo2
Originally Discovered by Leonardo Sembiring
Melialamath Applications. Copyright © 2009.
See also : Indonesia Version

Smart solution : To solve the linear equation of modular arithmetic.
Comment : REALLY SMART SOLUTION

In the N-hour-clock-arithmetic basis, to solve the solution of linear equation Ax = B, follow the instructions below.

Instructions:

  1. Simplify the equation. Let A mod N = K, B mod N = L then the equation equivalent with Kx = L.
  2. Find the GCF (greatest common factor) of K and L, say C.
  3. Simplify the equation : Kx/C = L/C, say Px = Q.
  4. Find the GCF of coefficient of x, P and its pair (N-P), presented by GCF scheme. This scheme comprises of divisors, quotients, and remainders. If such GCF is not equal to 1 then there is no solution for the equation.
  5. Use the GCF scheme in step 4 to get the last remainder prior to zero remainder by replacing P with Q, and its pair (N-P) with (N-Q), while the quotients remain the same.
  6. The last remainder mod N in step 5 is the solution of the equation.

Example:
In the 12-hour-clock-arithmetic basis, the linear equation 5x = 11 can be solved by replacing the value x with all possible values (0, 1, 2, … , 11 as 12-modular basis), and yields x = 7 accordingly.

Solution :
Step 1
As 5 mod 12 = 5 itself, and 11 mod 12 = 11 itself, the equation equivalent with 5x = 11.

Step 2
Find the GCF for 5 and 11.
11 = 2 * 5 + 1
5 = 5 * 1 + 0 (zero remainder)
The last remainder prior to zero remainder is 1. Then GCF for 5 and 11 is 1.

Step 3
Simplify the equation 5x/1 = 11/1, we get the equation itself, 5x = 11.

Step 4
Find the GCF for coefficient of x, 5 and its pair (12-5)= 7.
7 = 1 * 5 + 2
5 = 2 * 2 + 1
2 = 2 * 1 + 0 (zero remainder)
Three rows above is GCF scheme for 5 and 7 where last row yields zero remainder. Since the GCF, last remainder prior to zero remainder, is equal to 1 then continue to the next step.

Step 5
Using the scheme in step 4, replace (12-5) = 7 with (12-11) = 1, and 5 with 11 respectively, while the quotients remain the same.
Row 1 :
1 = 1 * 11 + …….., yields the remainder = -10
Row 2 :
11 = 2 * (-10) + ………., yields the remainder = 31
Row 3 :
From GCF scheme in step 4, this row yields zero remainder. This row is not included in the calculation.

Therefore, the last remainder is 31.

Step 6
Hence, x = 31 mod 12 = 7.

Example:
In the 2009-modular-arithmetic basis, given the equation 2015x = 14. Find x.

Solution :
Step 1
As 2015 mod 2009 = 6, and 14 mod 2009 = 14 itself, then the equation equivalent with 6x = 14.

Step 2
Find the GCF for 6 and 14.
14 = 2 * 6 + 2
6 = 3 * 2 + 0 (zero remainder)
The last remainder prior to zero remainder is 2. Then GCF for 6 and 14 is 2.

Step 3
Simplify the equation 6x/2 = 14/2, we get the equation 3x = 7.

Step 4 :
Find the GCF for coefficient of x, 3 and its pair (2009-3) = 2006.
2006 = 668 * 3 + 2
3 = 1 * 2 + 1
2 = 2 * 1 + 0 (zero remainder)
Three rows above is GCF scheme for 3 and 2006 where last row yields zero remainder. Since the GCF, last remainder prior to zero remainder, is equal to 1 then continue to the next step.

Step 5
Using the scheme in step 4, replace (2009-3) = 2006 with (2009-7) = 2002, and 3 with 7 respectively, while the quotients remain the same.
Row 1 :
2002 = 668 * 7 + …….., yields the remainder = -2674
Row 2 :
7 = 1 * (-2674) + ………., yields the remainder = 2681
Row 3 :
From GCF scheme in step 4, this row yields zero remainder. This row is not included in the calculation.

Therefore, the last remainder is 2681.

Step 6
Hence, x = 2681 mod 2009 = 672.


Indonesia Version
Untuk menyelesaikan persamaan linier Ax = B pada sistem jam N-an, ikuti langkah-langkah berikut.

Petunjuk:

  1. Sederhanakan persamaan tersebut. Misalkan A mod N = K dan B mod N = L, maka persamaan tersebut ekuivalen dengan Kx = L.
  2. Tentukan FPB (faktor persekutuan terbesar) dari K dan L, misalkan C.
  3. Sederhanakan persamaan menjadi : Kx/C = L/C, misalkan Px = Q.
  4. Tentukan FPB dari koefisien x, P dan pasangannya (N-P), disajikan dalam skema FPB. Skema tersebut terdiri dari pembagi, hasil-bagi, dan sisa. Apabila FPB tersebut tidak sama dengan 1 maka tidak ada penyelesaian dari persamaan linier yang dimaksud.
  5. Gunakan skema pada langkah 4 untuk mendapatkan sisa terakhir sebelum sisa NOL dengan menggantikan P dengan Q, dan (N-P) dengan (N-Q), sedangkan hasil-bagi tetap sama.
  6. Sisa terakhir modulo N adalah penyelesaian dari persamaan linier yang dimaksud.

Contoh :
Pada sistem jam 2009-an, berapa nilai x yang memenuhi persamaan 2015x = 14?

Penyelesaian :
Langkah 1
Karena 2015 mod 2009 = 6, dan 14 mod 2009 = 14, maka persamaan tersebut ekuivalen dengan 6x = 14.

Langkah 2
Tentukan FPB dari 6 dan 14.
14 = 2 * 6 + 2
6 = 3 * 2 + 0 (sisa NOL)
Sisa terakhir sebelum sisa NOL adalah 2. Dengan demikian, FPB dari 6 dan 14 adalah 2.

Langkah 3
Sederhanakan persamaan 6x/2 = 14/2, diperoleh persamaan itu sendiri, 3x = 7.

Langkah 4
Tentukan FPB dari koefisien x, yaitu 3 dan pasangannya (2009-3) = 2006.
2006 = 668 * 3 + 2
3 = 1 * 2 + 1
2 = 2 * 1 + 0 (sisa NOL)
Tiga baris di atas adalah skema FPB dari 3 dan 2006, dimana baris terakhir menghasilkan sisa NOL. Karena FPB tersebut (sisa terakhir sebelum sisa NOL) sama dengan 1 maka lanjutkan ke langkah berikutnya.

Langkah 5
Dengan menggunakan skema pada langkah 4, gantikan (2009-3) = 2006 dengan (2009-7) = 2002, dan 3 dengan 7, sedangkan hasil-bagi tetap sama.
Baris 1 :
2002 = 668 * 7 + …….., menghasilkan sisa = -2674
Baris 2 :
7 = 1 * (-2674) + ………., menghasilkan sisa = 2681
Baris 3 :
Kesamaan tidak dihitung karena menghasilkan sisa NOL.

Dengan demikian, sisa terakhir sebelum sisa NOL adalah 2681.

Langkah 6
Dengan demikian, x = 2681 mod 2009 = 672.

Advertisements