Congruence of all integers n, 4^n and 1 +3n mod(9)?

  1. I just took a number theory midterm, the professor had a question the that said
    "Show by induction that for all integers n, 4[tex]^{n}[/tex] is congruent to 1 +3n mod(9).

    Now am I crazy or did the professor probably mean to say integers greater or equal to 0, or for any natural number n, ...

    couldn't you show a counter example for instance n = -2, such that the congruence is false?
  2. jcsd
  3. CRGreathouse

    CRGreathouse 3,682
    Science Advisor
    Homework Helper

    In number theory, it's not unusual to assume that variables are natural numbers unless otherwise specified. I don't really want to think about negative powers here, since:
    * There is no multiplicative inverse over natural numbers or integers
    * There is a multiplicative inverse over real numbers (x not 0)
    * There is sometimes a multiplicative inverse over Zp

    and there could be reason to work over any of these.
  4. The only residues are 1,4,7, so even if we use the inverses, it doesn't matter since

    [tex]\frac{1}{4}\equiv 7 mod 9[/tex]
  5. When you think about it, as a general rule, if a and Mod b are such that, a, b positive integers, and (a,b) =1, (they are relatively prime ) Then the powers of a Mod b form a cyclic group, i.e., every power of a has an inverse in the group.
    Last edited: Oct 6, 2007
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?
Similar discussions for: Congruence of all integers n, 4^n and 1 +3n mod(9)?