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

I just took a number theory midterm, the professor had a question the that said
"Show by induction that for all integers n, 4$$^{n}$$ 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?

CRGreathouse
Homework Helper
I just took a number theory midterm, the professor had a question the that said
"Show by induction that for all integers n, 4$$^{n}$$ 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?

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.

The only residues are 1,4,7, so even if we use the inverses, it doesn't matter since

$$\frac{1}{4}\equiv 7 mod 9$$

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: