Proving Congruence Sum: Positive Integer Mod 9

  • Thread starter dancergirlie
  • Start date
  • Tags
    Proof Sum
In summary, the conversation discusses proving that every positive integer is congruent to the sum of its digits (mod 9). The suggested solution involves representing the number as a sum of terms and proving that 9 divides each term. It is concluded that since 10^n is congruent to 1 (mod 9), 9 divides a_n*10^n and a_n is not necessarily congruent to anything.
  • #1
dancergirlie
200
0

Homework Statement



Prove that every positive integer is congruent to the sum of its digits (mod 9). (for example 38 is congruent to 11(mod 9))

Homework Equations



If a is congruent to b (mod n), then n divides (a-b)

The Attempt at a Solution



let a= {a1, a2... a9} be digits
where 0 is less than or equal to a which is less than 10

That is where i don't know where to go, i have these digits and I don't know how to show that when added together they = b(mod 9)
maybe i should do something about 9 divides some digits, but i have no clue.

Any suggestions or tips would be great =)
 
Physics news on Phys.org
  • #2
Let anan-1...a0 represent your number, where the ai are the digits. Another way of representing your number is [tex] 10^n a_n + \cdots + 10^0 a_0 [/tex]. So what you want to prove is that 9 divides [tex] (10^n a_n + \cdots + 10^0 a_0) - (a_n + \cdots + a_0) [/tex]
 
Last edited by a moderator:
  • #3
I know this may sound stupid, but how am I supposed to show that. Right now I have:

9 divides a_n (10^(n)-1 )+ a_(n-1) (10^(n-1)-1)+⋯a_1 (10-1).
How do i get that 9 divides that?
 
  • #4
Every term in [tex] a_n (10^n - 1) + a_{n-1} (10^{n-1} - 1) + \cdots + a_1 (10-1) [/tex] is of the form [tex] a_i (10^i -1) [/tex]. If you can prove that 9 divides any such term, then you are done.

Can you figure out how to prove that 9 divides [tex] a_i (10^i -1) [/tex] for all positive integers i?
 
  • #5
well a_1(10-1)= a_1(9), and 9 divides a_1(9). So does that mean that it divides all i? I thought that only would apply for n=1
 
  • #6
10 is congruent to 1 mod 9. Hence 10^n is congruent to 1 mod 9.
 
  • #7
Where does the a_n go? wouldn't (a_1)10 be congruent to 1 mod 9, meaning that a_n would be congruent to 1 mod 9?
 
  • #8
ok, nevermind, i just figured out that that doesn't matter because 9 divides both a_n10^n and also 9 divides just 10^n
 
  • #9
well (10^n -1) that is
 
  • #10
a_n doesn't have to be congruent to anything. The point is that (10^n-1) is divisible by nine, as HitMan-2 pointed out. So a_n*10^n is congruent to a_n mod 9.
 

Related to Proving Congruence Sum: Positive Integer Mod 9

1. What is the concept of "Proving Congruence Sum"?

"Proving Congruence Sum" is a mathematical concept that involves determining if two numbers or mathematical expressions are congruent, meaning that they have the same remainder when divided by a given number. In this case, we are specifically looking at positive integers and using the modulus operator (mod) with a value of 9. This helps us identify patterns and relationships between numbers and can be useful in solving various mathematical problems.

2. How do you prove congruence sum for positive integers mod 9?

To prove congruence sum for positive integers mod 9, we need to take the sum of the digits in each number and determine if they have the same remainder when divided by 9. If the remainder is the same, then the two numbers are congruent. For example, 12 and 21 are congruent mod 9 because 1+2=3 and 2+1=3, both of which have a remainder of 3 when divided by 9.

3. Why is the modulus operator important in proving congruence sum?

The modulus operator, denoted by "mod", is important in proving congruence sum because it allows us to focus on the remainder when dividing by a specific number (in this case, 9). This helps us identify patterns and relationships between numbers, making it easier to prove congruence and solve mathematical problems.

4. What is the significance of using positive integers in proving congruence sum mod 9?

The use of positive integers in proving congruence sum mod 9 is significant because this allows us to focus on the patterns and relationships between numbers without the added complexity of negative numbers. It also aligns with the concept of congruence, which is based on the similarity or equivalence of numbers.

5. How is proving congruence sum mod 9 relevant in real-life applications?

There are many real-life applications where proving congruence sum mod 9 can be useful. For example, it can be used in coding and encryption algorithms, in data compression and error detection, and even in music theory. In these applications, understanding the relationship between numbers and identifying patterns can help improve efficiency and accuracy.

Similar threads

  • Calculus and Beyond Homework Help
Replies
27
Views
2K
Replies
4
Views
468
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
Back
Top