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


by mgiddy911
Tags: congruence, integers, mod9
mgiddy911
mgiddy911 is offline
#1
Oct4-07, 11:36 AM
P: 332
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?
Phys.Org News Partner Science news on Phys.org
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city
CRGreathouse
CRGreathouse is offline
#2
Oct4-07, 12:02 PM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by mgiddy911 View Post
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?
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.
robert Ihnot
robert Ihnot is offline
#3
Oct5-07, 08:14 PM
PF Gold
P: 1,059
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]

robert Ihnot
robert Ihnot is offline
#4
Oct6-07, 03:11 AM
PF Gold
P: 1,059

Congruence of all integers n, 4^n and 1 +3n 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.


Register to reply