
Algebra PreAlgebra and Basic Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
April 7th, 2014, 11:59 AM  #1 
Newbie Joined: Apr 2014 From: Pleven Posts: 2 Thanks: 0  divisibility by 3
Hello everybody. My english is very bad, but I`m gonna try to explain my question.I want to ask if someone could explain why every number eg 142 536 whent we are subtracting from it his reversed in the case 635 241 is always evenly divisible by 3(there is no remainder). If anyone can help with the answer I'm grateful, and if someone finds an exception  not the guts Example: 142 536  635 241=492 705:3=164 235 That is true for every integer number! I also have wrote an appication to test this. If a number is not evenly divisible by 3 the program would have to print it, but I waited 1 hour and refused to wait because I do not think it is possible my dualcore processor to complete the task soon(in the near one year ). Nothing printed. If someone sees bugs please to share. Console application with C #  handy was my Visual Studioit. If someone can help also to improve the algorithm. With other arguments the program checked 100 000 000 numbers for about 20 seconds. I have waited for about an hour which means it checked 18 000 000 000 numbers. Here is the code. using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; public class Alpha { // This method that will be called when the thread is started public void Beta() { check(0, 4223372036854775800); } public void Gama() { check(4223372036854775801, 9223372036854775800); } static void check(long startNumber,long endNumber) { long digit; for (digit = startNumber; digit < endNumber; digit++) { if ((digit  reverse(digit)) % 3 != 0) { Console.WriteLine(digit); } } } static long reverse(long digit) { long r; //ulong digit = 113240; long left = digit; long temp = 0; while (left > 0) { r = left % 10; temp = temp * 10 + r; left = left / 10; //left = Math.floor(left / 10); } return temp; } }; namespace digitTester { class Program { static void Main(string[] args) { Alpha oAlpha = new Alpha(); Alpha uAlpha = new Alpha(); Thread oThread = new Thread(new ThreadStart(oAlpha.Beta)); Thread uThread = new Thread(new ThreadStart(oAlpha.Gama)); // Start the thread oThread.Start(); uThread.Start(); oThread.Join(); uThread.Join(); Console.WriteLine("Finish!"); Console.ReadLine(); } } } Last edited by nicksona; April 7th, 2014 at 12:18 PM. 
April 7th, 2014, 12:17 PM  #2 
Newbie Joined: Apr 2014 From: Pleven Posts: 2 Thanks: 0 
Found the answer. If our number is abcd then we have 1000a + 100b + 10c + d. Whe are gonna subtract dcba from it which is 1000d + 100c + 10b +a 1000a + 100b + 10c + d (1000d + 100c + 10b +a)=1000a + 100b + 10c + d  1000d  100c  10b  a =999a + 90b  90c  999d= 9(111a + 10b  10c  111d) 
April 7th, 2014, 12:35 PM  #3 
Senior Member Joined: Jul 2010 From: St. Augustine, FL., U.S.A.'s oldest city Posts: 12,211 Thanks: 522 Math Focus: Calculus/ODEs 
You will find such a difference is in fact always divisible by 9. Consider the $n$digit decimal number: $\displaystyle N=\sum_{k=0}^n\left(a_k10^k \right)$ And so the difference D you describe is: $\displaystyle D=\sum_{k=0}^n\left(a_k10^k \right)\sum_{k=0}^n\left(a_{k}10^{nk} \right)$ $\displaystyle D=\sum_{k=0}^n\left(a_k\left(10^k10^{nk} \right) \right)$ $\displaystyle D=\sum_{k=0}^n\left(a_k10^{nk}\left(10^{2kn}1 \right) \right)$ A power of ten less 1 is always divisible by 9, and we see that each term has such a factor. 
April 7th, 2014, 12:40 PM  #4 
Math Team Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 234 
An integer is divisible by 3 IF AND ONLY IF the sum of the digits is divisible by 3. The sum of the digits of an integer is called the digital root , example $$DR(142536) = 1+ 4+ 2+ 5 +3 +6 = 21 $$ The $DR$ is iterative. $$DR( 142536) = DR(21) = 2 + 1 = DR(3)$$ 21 is divisible by 3 , that makes 142536 divisible by 3 and furthermore , those digits in any order would form a number divisible by 3. Iteration helps when the number has many digits , you apply the $DR$ procedure until the answer becomes obvious , technically until you get a single digit ... that single digit is then the true $DR$. 
April 7th, 2014, 05:31 PM  #5 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,700 Thanks: 2682 Math Focus: Mainly analysis and algebra 
That doesn't quite answer the question, since not every number has the digital root 3 and we want to know about the digital root of the difference between two numbers containing the same digits. You need to prove that $DR(a  b) \equiv DR(a)  DR(b) \mod 3$. 
April 7th, 2014, 10:27 PM  #6 
Math Team Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 234 
The $DR$ of any positive integer is a single digit from 1 to 9 ($DR(0) = 0$) So it is quite easy to observe that 3 and 9 are the only contestants that work for the relation $$DR(a  b) = DR(a)  DR(b)$$ by eliminating the other contestants with counterexamles. I make no claim that what follows is a rigorous proof. Counterexample to contestant 2 $$2 = DR(3  1) = DR(30)  DR(01)$$ $$30  01 = 29$$ NOT divsible by 2 Counterexample to contestant 4 $$4 = DR(5  1) = DR(50)  DR(01)$$ $$50  01 = 49$$ NOT divsible by 4 Counterexample to contestant 5 $$5 = DR(6  1) = DR(60) DR(01) $$ $$60  01 = 59$$ NOT divsible by 5 Counterexample to contestant 6 $$6 = DR(7  1) = DR(70) DR(01)$$ $$70  01 = 69$$ NOT divsible by 6 (but divisible by 3 ) Continue like this to eliminate contestants 7 and 8. Now , if we try to eliminate contestants 3 and 9 using this procedure we find it impossible to construct a counterexamle. IF the statement for 3 , 9 does not hold , THEN there should exst a counterexamle. Since a counterexamle is impossible then the statement for 3 , 9 must hold. Also , If $DR(a  b) = DR(a)  DR(b) = 0 , 3 , 6 , 9$ Then divisibility by 3 is gauranteed , no matter what positive integer values for a , b Finally , an answer to his question totally (If i have not misunderstood) Since he reverses digits and subtracts we can write $$DR(a  b) = DR(a)  DR(a) = 0$$ And 0 is divisible by 3 We do not need to know the numerical value of any DR , which is a bit surprising. Note $DR(a) = DR(b)$ 3 is really quite special IMHO. As MarkFL has pointed out , the OP procedure gaurantees that the number obtained is divisible by 9 BUT as far as $DR$ is concerned we need to throw out $DR(ab) = 3 , 6$ If i made mistakes i apologize. 
April 7th, 2014, 10:36 PM  #7 
Senior Member Joined: Apr 2014 From: Greater London, England, UK Posts: 320 Thanks: 156 Math Focus: Abstract algebra 
In general … Lemma: Take a number and swap any two of its digits. Then the difference between the old and new numbers is divisible by 9. Proof: Similar to the one by MarkFL. Corollary: Take a number and permute its digits in any way. Then the difference between the old and new numbers is divisible by 9. Proof: Follows from the fact that any permutation is a product of transpositions. For example: $$321123\,=\,198\,=\,9\times22$$ $$321132\,=\,189\,=\,9\times21$$ $$321213\,=\,108\,=\,9\times12$$ $$321231\,=\,90\,=\,9\times10$$ $$321312\,=\,9\,=\,9\times1$$ $$321321\,=\,0\,=\,9\times0$$ 

Tags 
divisibility 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Divisibility  yo79  Math Events  2  February 23rd, 2013 05:03 AM 
Divisibility  nukem4111  Number Theory  3  February 15th, 2013 05:19 PM 
divisibility  panky  Algebra  4  October 17th, 2011 05:06 PM 
Divisibility  PaulinaAnna  Algebra  4  September 8th, 2010 07:36 AM 
Divisibility  brangelito  Number Theory  2  May 25th, 2010 11:34 AM 