(I) N is a duodecimal (base 12) 50 digit positive integer of the form XX....Y, where X is repeated precisely 49 times followed by Y, such that N is divisible by the duodecimal number 137. Each of X and Y is a different duodecimal digit from 1 to B.

Determine the possible value(s) of N.

(II) P is a duodecimal (base 12) 50 digit positive integer of the form XX....Y, where X is repeated precisely 49 times followed by Y, such that P is divisible by the duodecimal number 147. Each of X and Y is a different duodecimal digit from 1 to B.

Determine the possible value(s) of P.

Working in base 12 throughout, and for part I only:

1.137 = B*15 (both primes). 10^42 is 1 followed by 42 zeros; deducting 1 from that gives a string of 42 B's, which is naturally divisible by B, giving a string of 42 1's. Call that unwieldy number N1. N1 can now be multiplied by j = {1,2,...B} to provide the 'X' digits of N, with some number k between 0 and B being added or subtracted to generate Y (which is assumed to be different from X).

2. To satisfy the requirement of divisibility, jN1+/-k must be 0, mod B and also 0, mod 15. We know that 10^n = 1 mod B for every value of n. So N1 = 42 mod B which is congruent to 6 mod B; accordingly for (j=1,k=5), jN1+k = 0.

3.1 It follows from 2 by successive multiplication of j*k, and representation of their product, mod B, that the following numbers are congruent to 0, mod B:

{(j=1,k=5),(j=2, k=A),(j=3,k=4),(j=4,k=9),(j=5,k=3),(j=6,k=8),(j=7,k=2), (j=8,k=7), (j=9,k=1), (j=A,k=6),(j=B,k=0)}.

3.2 But where (j+k)>10, we must deduct rather than add, to avoid changing the 10's column:
(j=1,k=5),(j=2, k=A) write k=-1,(j=3,k=4),(j=4,k=9) write k=-2,(j=5,k=3),(j=6,k=8) write k=-3,(j=7,k=2), (j=8,k=7) write k=-4,(j=9,k=1), (j=A,k=6) write k=-5,(j=B,k=0).

3.3 This gives the last digit-pairs as{1..16,2..21,3..37,4..42,5..58,6..63,7..79,8..84,9..9A,A..A5,B..B0} so that these are the only numbers that require testing for divisibility by 15.

4. 10 and 15 are relatively prime,and 15 is prime, so that no power of 10 is divisible by 15, and checking the residues for small powers of 10 confirms that 10^n mod 15 will cycle through all values between 1 and 14 before repeating. Using the theorem a^(p-1)  is congruent to 1(mod p) we can determine that 10^14 and hence also 10^40 leave a remainder of 1, mod 15. Since this is 3 complete cycles of values, pairing the residues Gauss-fashion informs us that a string of 40 1's is divisible by 15; that 41 1's leave a residue of 1, and hence that 42 1's leave a residue of (1+10) =11. We can now apply similar reasoning as in 3 to produce the pairs {(j=1,k=4),(j=2,k=8),(j=3,k=10)...etc} obtaining residues of {1,8,9,16,0,7,8,15,16,6,13)

5. It follows that only 5...58 is divisible by 137.

Edited on November 7, 2010, 8:22 am

Posted by broll on 2010-11-07 06:10:43