Register to reply

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

by mgiddy911
Tags: congruence, integers, mod9
Share this thread:
mgiddy911
#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
What lit up the universe?
Sheepdogs use just two simple rules to round up large herds of sheep
Animals first flex their muscles
CRGreathouse
#2
Oct4-07, 12:02 PM
Sci Advisor
HW Helper
P: 3,684
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
#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
#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