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
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
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