Results 1 to 3 of 3

Math Help - 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.

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

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

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

    If the digits of the number are,
    A_1A_2...A_n
    Then define a polynomial,
    P(x)=x^{n-1}A_1+...+xA_{n-1}+A_n
    Thus,
    P(10)=N
    And,
    P(1) is sum of digits.
    Thus,
    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
    11,911
    Thanks
    773
    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: a_na_{n-1}a_{n-2}\hdots a_1a_o

    Its value is: . 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: . S \:=\:a_n + a_{n-1} + a_{n-2} + \hdots + a_1 + a_0


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

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


    Since N - S is a multiple of 9: .  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: September 29th 2011, 08:24 PM
  2. x^6 congruent to 1 (mod 19)
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: March 2nd 2010, 07:54 PM
  3. Congruent Triangles
    Posted in the Geometry Forum
    Replies: 1
    Last Post: February 23rd 2010, 04:16 AM
  4. Congruent Triangles
    Posted in the Geometry Forum
    Replies: 6
    Last Post: December 29th 2008, 10:21 PM
  5. Congruent Angles
    Posted in the Geometry Forum
    Replies: 2
    Last Post: December 22nd 2008, 10:09 PM

Search Tags


/mathhelpforum @mathhelpforum