My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Thanks Tree10Thanks
  • 3 Post By MarkFL
  • 2 Post By agentredlum
  • 2 Post By agentredlum
  • 3 Post By Olinguito
Reply
 
LinkBack Thread Tools Display Modes
April 7th, 2014, 10:59 AM   #1
Newbie
 
Joined: Apr 2014
From: Pleven

Posts: 2
Thanks: 0

Question 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 dual-core 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 Studio-it. 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 11:18 AM.
nicksona is offline  
 
April 7th, 2014, 11:17 AM   #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)
nicksona is offline  
April 7th, 2014, 11:35 AM   #3
Senior Member
 
MarkFL's Avatar
 
Joined: Jul 2010
From: St. Augustine, FL., U.S.A.'s oldest city

Posts: 12,211
Thanks: 521

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^{n-k} \right)$

$\displaystyle D=\sum_{k=0}^n\left(a_k\left(10^k-10^{n-k} \right) \right)$

$\displaystyle D=\sum_{k=0}^n\left(a_k10^{n-k}\left(10^{2k-n}-1 \right) \right)$

A power of ten less 1 is always divisible by 9, and we see that each term has such a factor.
Thanks from agentredlum, Olinguito and nicksona
MarkFL is offline  
April 7th, 2014, 11:40 AM   #4
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

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$.

Thanks from MarkFL and nicksona
agentredlum is offline  
April 7th, 2014, 04:31 PM   #5
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,671
Thanks: 2651

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$.
v8archie is offline  
April 7th, 2014, 09:27 PM   #6
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

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(a-b) = 3 , 6$

If i made mistakes i apologize.

Thanks from MarkFL and nicksona
agentredlum is offline  
April 7th, 2014, 09:36 PM   #7
Senior Member
 
Olinguito's Avatar
 
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:

$$321-123\,=\,198\,=\,9\times22$$
$$321-132\,=\,189\,=\,9\times21$$
$$321-213\,=\,108\,=\,9\times12$$
$$321-231\,=\,90\,=\,9\times10$$
$$321-312\,=\,9\,=\,9\times1$$
$$321-321\,=\,0\,=\,9\times0$$
Thanks from MarkFL, agentredlum and nicksona
Olinguito is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

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 04:03 AM
Divisibility nukem4111 Number Theory 3 February 15th, 2013 04:19 PM
divisibility panky Algebra 4 October 17th, 2011 04:06 PM
Divisibility PaulinaAnna Algebra 4 September 8th, 2010 06:36 AM
Divisibility brangelito Number Theory 2 May 25th, 2010 10:34 AM





Copyright © 2019 My Math Forum. All rights reserved.