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

  • Thread starter mgiddy911
  • Start date
  • Tags
    Integers
In summary, The conversation was about a question on a number theory midterm that asked to show by induction that for all integers n, 4^{n} is congruent to 1+3n mod(9). The question was discussed whether it meant for all integers or only for natural numbers, and the possibility of a counterexample for n = -2 was brought up. The conversation also mentioned the use of multiplicative inverses and the fact that powers of a form a cyclic group under certain conditions.
  • #1
mgiddy911
335
0
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?
 
Physics news on Phys.org
  • #2
mgiddy911 said:
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.
 
  • #3
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
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:

1. What is the meaning of "congruence" in this context?

Congruence refers to a relationship between two numbers where their remainders after division by a given number are equal. In this case, we are looking at the congruence of all integers n, 4^n, and 1 + 3n mod(9).

2. Why are we specifically looking at the integers n, 4^n, and 1 + 3n mod(9)?

These integers have a special relationship when it comes to congruence mod(9). By examining their congruence, we can gain insights into the patterns and properties of these numbers.

3. What is the significance of using mod(9) in this study?

Mod(9) is used because it allows us to group numbers into classes based on their remainders after division by 9. This helps us to better understand the properties and relationships between these numbers.

4. Can you explain the notation "1 + 3n" in the equation?

The notation "1 + 3n" represents a sequence of numbers where each term is obtained by adding 3 to the previous term. For example, when n = 1, the sequence becomes 1, 4, 7, 10, etc.

5. How does the congruence of these numbers relate to real-world applications?

Congruence of numbers has many real-world applications, such as in cryptography, computer science, and engineering. By understanding the properties and relationships between numbers, we can develop algorithms, codes, and systems that are more efficient and secure.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
27
Views
2K
  • Precalculus Mathematics Homework Help
Replies
6
Views
952
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
654
Replies
4
Views
3K
  • Linear and Abstract Algebra
Replies
1
Views
3K
  • Topology and Analysis
Replies
6
Views
1K
  • General Math
Replies
2
Views
965
  • Linear and Abstract Algebra
Replies
4
Views
3K
Replies
4
Views
2K
Back
Top