Register to reply 
Congruence of all integers n, 4^n and 1 +3n mod(9)? 
Share this thread: 
#1
Oct407, 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? 


#2
Oct407, 12:02 PM

Sci Advisor
HW Helper
P: 3,684

* 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 Z_{p} and there could be reason to work over any of these. 


#3
Oct507, 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] 


#4
Oct607, 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 