Expert: Josh - 6/9/2004

Question
Maybe you can help me. I was given a homework assignment dealing with divisibility, bases, and justifications. I do not understand how to do these few problems, and my teacher does not answer questions when asked. I am going to list the questions and see if you can help me gain an understanding of it.

First, my question is about bases. 1210221 is written as a base three number and I need to write it as a base four number. He said first to make it a base ten number then to a base four number. How do I even begin to do this?

Second, divisibility is giving me a problem. The question that he gave says "Using the Divisibility Criteria, briefly explain why each of the following are true." Those questions are
a. 675 is divisible by 3
b.179842752 is divisible by 4
c. 7326426 is divisible by 6
d. 6055 is divisible by 7
e. 539484 is divisible by 11
How do I explain why this is true?

Next, I was given this problem:
((ab)c)d=(cb)(da). With this problem I need to put all the justifications and properties of integers in there to verify this. I do not understand this either.

Last, I need to list 12 consecutive positive integers in which none of them are prime. I dont understand the problem at all or what it is asking.

I know that this is a lot of questions but I am a junior in college and it has been 5 years since I have had a math and I am a little rusty but I need to do well on this homework because my final grade is depending on it.

If you could help me I would really appreciate it.

Thanks,
Ashley

Answer
Hey Ashley,

Let's talk about number representation in the metric system.

(I) NUMBER REPRESENTATION IN THE METRIC SYSTEM
Consider the number 1234. Literally, it contains 4 digits.
Translated to English, we refer to this quantity as one thousand two hundred and thirty four, right? What we are implicitly doing, is translating this expression as a linear combination of various units. Here, the relevant units are "1" (one), "10" (ten), "100" (hundred) and "1000" (thousand).

As you can readily check 1234=1*(1000)+2*(100)+3*(10)+4*(1). This is nothing more than a sum containing terms which are some multiple with respect to different base-10 units.

An equivalent representation is as follows:
1234=1*(10^3)+2*(10^2)+3*(10^1)+4*(10^0),
where 10^x denotes 10 raised to the power of x.
[We have 10^0=1, 10^1=10, 10^2=100, 10^3=1000 and so forth]
--------------------
(II) BINARY SYSTEM (base-2 number representation is used in all modern computers and in digital commmunication)
In this case, we represent numbers using
a[N]*(2^N)+...+a[2]*(2^2)+a[1]*(2^1)+a[0]*(2^0),
where a[n] is the nth coefficient correponding to base 2 raised to the power of n; where n=0,1,2,...,N etc.

eg., consider the binary number X=10111.
Here, a[4]=1,a[3]=0,a[2]=1,a[1]=1,a[0]=1.
Using the result above,
X=1*(2^4)+0*(2^3)+1*(2^2)+1*(2^1)+1*(2^0)
=1*16+0*8+1*4+1*2+1*1
=16+4+2+1
=23
Are you with me?
--------------------
Generalization: The Base-M representation for X would be
b[N]*(M^N)+b[N-1]*(M^(N-1))...+b[2]*(M^2)+b[1]*(M^1)+b[0]
same interpretation as before.
--------------------
(III) Ternary system (base-3 number representation)
Let X=1210221.
This is simply
X=1*(3^6)+2*(3^5)+1*(3^4)+0*(3^3)+2*(3^2)+2*(3^1)+1*(3^0)
=1*729+2*243+1*81+0*27+2*9+2*3+1*1
=1321 using your calculator.
--------------------
(IV) Converting to base-4 number

Let X_10=1321, the subscript _10 simply make it obvious that we are dealing with the metric system (base-10).
Task: To find X_4, i.e., express X with respect to base-4.

Algorithm (Numerical Recipe):
(1) Write down powers of 4.

(2) Let N be the degree of the polynomial
X=b[N]*(M^N)+b[N-1]*(M^(N-1))...+b[2]*(M^2)+b[1]*(M^1)+b[0]
Compute b[n] starting from n=N by:
Assigning the value "round_down{X/(M^N)}" to b[n]

(3) Update X with X-b[n]*(M^n) and decrease n by 1.
Then, repeat step(2), until n=0 is done.

Example:

(Step 1) 4^5=1024,4^4=256,4^3=64,4^2=16,4^1=4,4^0=1
[Note: we don't need anything larger than 4^6=4096, since X is obviously smaller than 4096, all higher coefficients corresponding to 4^6, 4^7 etc. will be zero!]

(Step 2) We have N=5, X=1321. So, start with n=5.
b[5]=round_down{1321/(4^5)}
   =round_down(1321/1024)
   =round_down(1.29)
   =1
(Step 3) Update X with 1321-b[5]*(4^5)
i.e., new X=1321-1*1024=297. [Keep this in mind]
Let N=4 and repeat procedure.

(Step 2) We have N=4, X=297. Let n=4.
b[4]=round_down{297/(4^4)}
   =round_down(297/256)
   =round_down(1.1602)
   =1 ...as it turns out!
(Step 3) Update X with 297-b[4]*(4^4)
i.e., new X=297-1*256=41. [Keep this in mind]
Let N=3 and repeat procedure.

(Step 2) We have N=3, X=41. Let n=3.
b[3]=round_down{41/(4^3)}
   =round_down(41/64)
   =round_down(0.6404)
   =0
(Step 3) No need to update X, since
new X=41-0*64=41.
However, let N=2 and repeat procedure.

(Step 2) We have N=2, X=41. Let n=2.
b[2]=round_down{41/(4^2)}
   =round_down(41/16)
   =round_down(2.5625)
   =2 ...getting something different this time.
(Step 3) Update X with 41-b[2]*(4^2)
i.e., new X=41-2*16=9. [Keep this in mind]
Let N=1 and repeat procedure.

(Step 2) We have N=1, X=9. Let n=1.
b[1]=round_down{9/(4^1)}
   =round_down(9/4)
   =round_down(2.25)
   =2
(Step 3) Update X with 9-b[1]*(4^1)
i.e., new X=9-2*4=1.
Finally, let N=0 and repeat procedure.

(Step 2) We have N=1, X=1. Let n=1. Quite obvious now that
b[0]=round_down{1/(4^0)}
   =1
(Step 3) Procedure terminates. Now, trace back the coefficients.

b[5]=1,b[4]=1,b[3]=0,b[2]=2,b[1]=2,b[0]=1
So, X_4=110221

Always CHECK that we haven't made any mistake.
1*1024+1*256+2*16+2*4+1*1=1321.
So, this is indeed correct.
===================
(V) DIVISIBILITY CRITERION

One way to check whether X is divisible by M is as follows.
Obtain the base-M representation using the method above.

THEOREM:
--------
Observe that X=b[N]*(M^N)+b[N-1]*(M^(N-1))...+b[2]*(M^2)+b[1]*(M^1)+b[0]
and b[1] refers to multiples of "M".
By definition, if X is NOT divisble by M, it has a reminder "r" smaller than M. That is, the smallest coefficient in the base-M representation, b[0], will be NON-ZERO.

Pick something simple to check this.
(eg.1) Consider whether 28 is divisible by 3 (we know the answer, that it is not divisible by 3).

X=28, in base 3, X_3=1*27+0*9+0*3+1*1.
X_3=1*(3^3)+0*(3^2)+0*(3^1)+1*(3^0).
Importantly, the coefficient b[0]=1, not zero, so X=28 is NOT divisible by 3. Clear?

(eg.2) For instance, is X=7299 divisible by 9?
First, find base-9 representation for X.
You can show that X=1*(9^4)+1*(9^3)+1*(9^1)+0*(9^0).
Since b[0]=0, it is divisible by 0.

Note: You must explain what you mean by b[0] in your answer, since this is not something that is known to everyone. So, you need to set up the problem properly, as I've done. Refer to the theorem stated above.

Note2: As a check, for smaller numbers that your calculator can handle, you can always try dividing X by M to see whether it returns a floating point number (i.e, one with trailing decimal figures). But that is beside the point of the exercise.
==================
(VI) APPEALING TO THE 12 FUNDAMENTAL MATHEMATIC AXIOMS
Assuming that a,b,c,d all belong to the field of real numbers, R.
((ab)c)d=(abc)d ...simple expansion
       =abcd
       =acbd   ...using the commutative property
       =ac(bd) ...associative law of multiplication
       =(bd)ac ...using the commutative property
       =c(bd)a ...commutative property again
       =(cb)(da)...using the associative property.
===================
(VII) Consecutive numbers refer to a string of natural numbers appearing in increasing order, each differ from the previous number by 1. eg., five arbitrary consecutive numbers are {3,4,5,6,7}

In your problem, algebraically, you need to find a number N such that {N,N+1,N+2,N+3,...N+11} are all prime numbers. i.e., not divisible by any number smaller than itself, other than 1.

Simplest approach is to list a finite number of known prime numbers and see if you can find a gap between two prime numbers larger than 12.
Hints:
All even numbers, except 2 are non-prime.
All numbers larger than 5, with digit ending in 0 or 5 are non-prime.
Consequently, x2, x4, x5, x6, x8, x0 must be non-prime.

All you need to check is that the numbers x1, x3, x7, x9 in between these are also non-prime, so that you get a run of 12 numbers.

Some of the primes are 2,3,5,7,11,13,17,19,23,29,31,37,...
Again 41 breaks the run, so you have to keep searching.

All right, I'm in a good mood, i'll help you with this one.
The smallest feasible solution is the string of numbers between the two primes 113 and 127. (N.B. many solutions possible)

How do I know this?
(1) The first 1000 primes are listed at http://www.utm.edu/research/primes/lists/small/1000.txt
(2) Organize this into an array
(3) Compute the first order difference and perform a linear search.

Good night:)