Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 4, 2007 #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. Oct 4, 2007 #2


    User Avatar
    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. Oct 5, 2007 #3
    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. Oct 6, 2007 #4
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for Congruence integers
I Linear mapping of a binary vector based on its decimal value