Expert: Josh - 6/3/2006

Question
Find prime numbers p such that        
   p p p
   X p p
-----------------
 p p p p
p p p p 0
--------------------
p p p p p
---------------------     these prime numbers may be different
This above equation shows a multiplication sum/process going on.

Answer
Moksh Aggarwal Asks
Subject:  find p
Question:  Find prime numbers p such that        
  p p p
  X p p
-----------------
p p p p
p p p p 0
--------------------
p p p p p
---------------------     these prime numbers may be different
This above equation shows a multiplication sum/process going on.

---
Moksh Aggarwal,

I didn't answer this question the first time, because I wanted you to think about this more. I was hoping that you would make some personal observations and share these with me.

The question should have stated the implicit assumption that "p" is a single digit prime number.

If we look at the set of prime numbers, P={2,3,5,7,11,13,17 etc}, it's fair to rule out everything other than 2,3,5 and 7.

Note: Remember that 1 is not a prime number.

I am now going to guide you through this problem.
It's quite involved! So, you must be patient.
I'll show you that the answer to this problem is NOT unique. i.e., there is more than one solution.

Now, I have to ask you to be very patient:)
============================================
PART 1: Initial thought experiment
(This is not actually the right way of answering the question, but it does give us some insight.)

Let's assume that we are multiplying "ppp" by "pp" to obtain a 5 digit number "ppppp".

Let's pick on the last digit in "ppppp". Applying the rules of multiplication, the last digit "p" must be the product of "p" (the last digit in "ppp") and "p" (the last digit in "pp"). This constraint allows us to get a little closer to the answer.

Clearly, 2*2=4 does not fit this criterion. We need p*p=Ap, we don't care what the prefix string "A" represents.

Also, 3*3=9. Again, this does not fit the pattern. Similarly, we can rule out p=7, since 7*7=49. This is inconsistent with the requirement p*p=Ap, for some numerical prefix A. Thus, we conclude that p=5.

=============================================
PART 2: Proper way of formulating this problem
.....
Actually, we want to produce a 5 digit number, where all the digits are prime numbers. This should have been clearly stated. Be careful. The symbolic representation given in the question (identical p's) can easily lead us to the WRONG path.

Let us instead formulate the problem as
abc * de = fghij, where a,b,c,d,e,f,g,h,i,j are single digit prime numbers.

Expanding the multiplicative (also called convolution) sum, we get
abc * de = (100ae+10be+ce) + (1000ad+100bd+10cd+0)
= ad*1000 + (bd+ae)*100 + (cd+be)*10 + ce ....[#1]

Explanation: In the first line, recall that a number like 876 may be represented as 8*100+7*10+6*1. Here, ce is a true multiplication between two sigle digits "c" and "e"; not simply a concatenated string. In the second line, we gather coefficients corresponding to the same power of 10. This is the basis for the metric representation.

Now, things start to get much more complicated, because we have to take "overflow" into account when we add numbers. Example: when we add 5 and 7, we get 12. The "1" no longer stays in place, but is popped-up to the next digit. Thus, if we consider 85+7, we get 92. The digit 9 is actually an accumulation of 8 and the carry-over digit "1". You really need to understand how an adder works to fully appreciate this. This is standard university material in a first year "digital circuit" or computer engineering course. I have no idea why anyone would set you such a question, without proper explanation of "adder propagation" mechanisms. Other than trial-and-error, a high school student cannot be expected to solve this problem formally.

To proceed, we need to introduce the modulo function, mod(N,m), which finds the remainder when N is divided by m. For example, if N=13, m=10, then, mod(13,10)=3. If N=212, m=100, then, mod(212,100)=12.

Now, we derive algebraic expressions which relate the result from long multiplication (in [#1]) with each of the digits in the string "fghij". During this process, we take into account the carry-over effect during adding. This is all I'm going to say, I won't get into the nitty gritty details. It can be shown that:

j=mod(ce,10)
Let quotient q=(ce-j)/10 be the carry over digit.

i=mod(cd+be+q,10)
Let quotient r=(cd+be+q-i)/10.

h=mod(bd+ae+r,10)
Let quotient s=(bd+ae+r-h)/10.

g=mod(ad+s,10)
Let quotient t=(ad+s-g)/10 be the carry over digit.
In this case, it must be "f".

In summary, our solution needs to satisfy the following constraints:
j=mod(ce,10),
i=mod(cd+be+q,10), where q=(ce-j)/10.
h=mod(bd+ae+r,10), where r=(cd+be+q-i)/10.
g=mod(ad+s,10), where s=(bd+ae+r-h)/10.
f=(ad+s-g)/10
AND all single digits f,g,h,i,j must be prime. [#2]

==============================================
PART 3: Solving the problem

a) Using the observation in part one, we attack the first condition j=mod(ce,10).

Forming the following products between "c" and "e":
ce=[2*2, 2*3, 2*5, 2*7, 3*3, 3*5, 3*7, 5*5, 5*7]
 =[ 4,   6 ,  10,  14,   9,  15,  21,  25,  35]
mod(ce,10)=[4,6,0,4,9,5,1,5,5].
Only the sixth, eighth and nineth combination of "c" and "e" actually produces a valid prime j.

The only feasible solutions thus far are:
c=3, e=5 or c=5, e=3,
c=5, e=5,
c=5, e=7 or c=7, e=5.

We can continue this process, checking the other conditions and narrowing our solution space. This is best done using a numerical package or some scientific programming language.

An algorithm is provided in the appendix (after the results section). It basically checks all the conditions previously found in part two (see [#2]).

Results: The solutions include
a=3,b=2,c=5,d=7,e=3,fghij="23725"
a=3,b=3,c=7,d=7,e=5,fghij="25275"
a=3,b=5,c=5,d=7,e=7,fghij="27335"
a=3,b=7,c=5,d=7,e=3,fghij="27375"
a=5,b=7,c=5,d=5,e=7,fghij="32775"
a=7,b=2,c=5,d=3,e=5,fghij="25375"
a=7,b=3,c=5,d=3,e=5,fghij="25725"
a=7,b=3,c=7,d=7,e=5,fghij="55275"
a=7,b=7,c=5,d=3,e=3,fghij="25575"

Exercise: Check that "abc"*"de" gives "fghij"

Cheers:)
================================================
APPENDIX: AN ALGORITHM

p=[2,3,5,7]';

for n1=1:length(p)
 a=p(n1);
 for n2=1:length(p)
   b=p(n2);
   for n3=1:length(p)
     c=p(n3);
     for n4=1:length(p)
       d=p(n4);
       for n5=1:length(p)
         e=p(n5);
         j=mod(c*e,10);
         if ~isempty(find(p==j)) %check if j is prime
           q=(c*e-j)/10;
           i=mod(c*d+b*e+q,10);
           if ~isempty(find(p==i)) %check if i is prime
             r=(c*d+b*e+q-i)/10;
             h=mod(b*d+a*e+r,10);
             if ~isempty(find(p==h)) %check if h is prime
               s=(b*d+a*e+r-h)/10;
               g=mod(a*d+s,10);
               if ~isempty(find(p==g))
                 f=(a*d+s-g)/10;
                 if ~isempty(find(p==f))
                   disp(sprintf('a=%d,b=%d,c=%d,d=%d,e=%d,fghij="%d%d%d%d%d"',a,b,c,d,e,f,g,h,i,j))
                 end
               end
             end
           end
         end
       end
     end
   end
 end
end