Results 1 to 3 of 3

Thread: congruent mod 9

  1. #1
    Member
    Joined
    Nov 2006
    Posts
    123

    Question congruent mod 9

    question

    Prove that every integer is congruent mod 9 to the sum of its digits.

    Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Jenny20 View Post
    question

    Prove that every integer is congruent mod 9 to the sum of its digits.

    Thank you very much.
    There is a useful theorem.

    $\displaystyle a\equiv b (\mbox{ mod } n)$
    Then,
    $\displaystyle P(a)\equiv P(b) (\mbox{ mod } n)$.

    Where $\displaystyle P(x)$ is some polynomial in $\displaystyle \mathbb{Z}[x]$.

    Thus, we know that,
    $\displaystyle 10\equiv 1 (\mbox{ mod }n)$.

    If the digits of the number are,
    $\displaystyle A_1A_2...A_n$
    Then define a polynomial,
    $\displaystyle P(x)=x^{n-1}A_1+...+xA_{n-1}+A_n$
    Thus,
    $\displaystyle P(10)=N$
    And,
    $\displaystyle P(1)$ is sum of digits.
    Thus,
    $\displaystyle N\equiv \mbox{ SUM }(\mbox{ mod }n)$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, Jenny!

    Here's a more "primitive" proof . . .


    Prove that every integer is congruent mod 9 to the sum of its digits.

    We have an integer of the form: $\displaystyle a_na_{n-1}a_{n-2}\hdots a_1a_o $

    Its value is: .$\displaystyle N \:=\:10^na_n + 10^{n-1}a_{n-1} + 10^{n-2}a_{n-2} + \hdots + 10a_1 + a_o$

    The sum of its digits is: .$\displaystyle S \:=\:a_n + a_{n-1} + a_{n-2} + \hdots + a_1 + a_0$


    Consider their difference:
    . . $\displaystyle N - S \;=\;(10^n-1)a_n + (10^{n-1}-1)a_{n-1} + (10^{n-2}-1)a_{n-2} + \hdots$$\displaystyle + (10^2-1)a_2 + (10-1)a_1 $

    All the coefficients are of the form: $\displaystyle 10^k-1 \:=\:999\hdots9$
    . . and hence are divisible by 9.


    Since $\displaystyle N - S$ is a multiple of 9: .$\displaystyle N \equiv S \pmod 9$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is S_3 congruent to D_3?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Sep 29th 2011, 07:24 PM
  2. x^6 congruent to 1 (mod 19)
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: Mar 2nd 2010, 06:54 PM
  3. Congruent Triangles
    Posted in the Geometry Forum
    Replies: 1
    Last Post: Feb 23rd 2010, 03:16 AM
  4. Congruent Triangles
    Posted in the Geometry Forum
    Replies: 6
    Last Post: Dec 29th 2008, 09:21 PM
  5. Congruent Angles
    Posted in the Geometry Forum
    Replies: 2
    Last Post: Dec 22nd 2008, 09:09 PM

Search Tags


/mathhelpforum @mathhelpforum