home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / math / 17246 < prev    next >
Encoding:
Internet Message Format  |  1992-12-21  |  2.8 KB
  1. Path: sparky!uunet!spool.mu.edu!think.com!ames!pacbell.com!network.ucsd.edu!munnari.oz.au!comp.vuw.ac.nz!canterbury.ac.nz!equinox.gen.nz!equinox!bignode!pete
  2. From: pete@bignode.equinox.gen.nz (Pete Moore)
  3. Subject: Re: Multiples of 9
  4. Newsgroups: sci.math
  5. References: <1992Dec18.165248.10914@vax.oxford.ac.uk>
  6. Organization: Equinox Networks
  7. Reply-To: pete@bignode.equinox.gen.nz
  8. X-Newsreader: TIN [version 1.1 PL8]
  9. Message-ID: <pete.03kt@bignode.equinox.gen.nz>
  10. Date: 21 Dec 92 16:51:22 +1200
  11. Organization: Equinox Networks
  12. Lines: 53
  13.  
  14. mingos@vax.oxford.ac.uk wrote:
  15.  
  16. >  I hope I'm posting this into the correct maths group, but I have a problem
  17. >which has started bugging me, it may be an old chestnut, but I can't find a 
  18. >solution that satisfies me.
  19.  
  20. >  The basic thing is that if you multiply any number by 9, you end up with a
  21. >number whose digits add up to 9, OR whose digits add up to a number whose
  22. >digits add up to 9, OR...etc, depending on how big the number is.
  23. >  so, for example, 9x12343 = 111087.  1+1+1+0+8+7 = 18.  1+8 = 9.
  24.  
  25. >  I can figure a real hand waving argument for this, but does anyone have a
  26. >more definitive proof, or can point me towards one?  I'm a chemist by
  27. >background, so I don't know my way around the mathematical lit.  I don't even
  28. >know which branch of mathematics this is...
  29.  
  30. It's number theory.
  31.  
  32. First I'll explain congruences, in case you aren't familiar with them.
  33. I'll use # for the congruence symbol (nomally written like = but with 3
  34. horizontal lines instead of 2), i.e. I'll write
  35.   a # b (mod c)
  36. to mean that a - b is an integer multiple of c. In particular, a#0 (mod 9)
  37. if and only if a is a multiple of 9.
  38.  
  39. Some relevant properties of congruences:
  40.   (1) a + b  #  {a (mod c)} + {b (mod c)}   (mod c)
  41.   (2) a * b  #  {a (mod c)} * {b (mod c)}   (mod c)
  42.   (3) 10 # 1 (mod 9)  and so  10^k # 1 (mod 9) for any positive
  43.              integer k, by applying (2) repeatedly
  44.  
  45. Suppose n has k base-10 digits. Let these digits (in order) be  a_1, a_2,
  46.  ... a_k
  47.  
  48. Then  n = a_1*10^{k-1} + a_2*10^{k-2} + ... + a_{k-1}*10 +a_k
  49.  
  50. Using (1)-(4) above, n # a_1 + a_2 + ... + a_k  (mod 9)  and hence n is
  51. divisible by 9 (i.e. n#0 (mod 9)) if and only if the sum of the digits of n
  52. is divisible by 9 (and this sum is divisible by 9 iff the sum of _its_
  53. digits is divisible by 9, etc).
  54.  
  55. Example:
  56.  
  57.   let   n = 5283 then a_1=5, a_2=2, a_3=8, a_4=3,
  58.    and  n = 5*10^3 + 2*10^2 + 8*10 + 3
  59.    so   n # 5+2+8+3 = 18 (mod 9), since the powers of 10 are # 1 (mod 9).
  60.    But  18#0 (mod 9), and so 5283 _is_ divisible by 9.
  61. --
  62.  +-------------------  pete@bignode.equinox.gen.nz  -------------------+
  63.  | The effort to understand the universe is one of the very few things |
  64.  | that lifts human life above the level of farce, and gives it some   |  
  65.  | of the grace of tragedy   -  Steven Weinberg                        |
  66.  +---------------------------------------------------------------------+
  67.