Number Theory with modular arithmetic

In summary, the conversation involves proving that the expression \frac{(a_1a_2...a_n)^2 - 1}{8} is an integer when n \geq 2 and a_1,a_2,...,a_n are odd numbers. The conversation also discusses different approaches to proving this, including using a previous problem and representing the a's as 2k+1. Eventually, it is realized that the expression is already in a form that can be proven using a previous result.
  • #1
CornMuffin
55
5

Homework Statement


When a is odd, show [tex]\frac{a^2-1}{8}[/tex] is an integer. Then prove by induction [tex]n \geq 2[/tex] that for all odd numbers [tex]a_1,a_2,...,a_n,[/tex]

[tex]
\frac{(a_1a_2...a_n)^2 - 1}{8} \equiv \frac{a^2_1 - 1}{8} + \frac{a^2_2 - 1}{8} + ... + \frac{a^2_n - 1}{8} \ mod \ 2
[/tex]

Homework Equations


The Attempt at a Solution


I proved that [tex]\frac{a^2-1}{8}[/tex] is an integer for odd a without much difficulty, but I am having trouble even proving the base case, n=2 for this.

From a previous problem, I already proved [tex]\frac{(a_1a_2...a_n) - 1}{2} \equiv \frac{a_1 - 1}{2} + \frac{a_2 - 1}{2} + ... + \frac{a_n - 1}{2} \ mod \ 2[/tex] for odd a. So I thought I might be able to use that and separate it into [tex]\frac{(a_1a_2...a_n) - 1}{2}[/tex] and [tex]\frac{(a_1a_2...a_n) + 1}{4}[/tex] but that didn't get me anywhere. I also tried representing the a's as 2k+1 for an integer k. But I just can't get anywhere.

Also, I figure that if I can prove that the left and right hand sides are both odd or both even, then I am done.
 
Physics news on Phys.org
  • #2
Isn't

[tex]

\frac{(a_1a_2...a_n)^2 - 1}{8} \equiv \frac{a^2_1 - 1}{8} + \frac{a^2_2 - 1}{8} + ... + \frac{a^2_n - 1}{8} \ mod \ 2

[/tex]

already in the form

[tex]
\frac{(b_1b_2...b_m) - 1}{2} \equiv \frac{b_1 - 1}{2} + \frac{b_2 - 1}{2} + ... + \frac{b_m - 1}{2} \ mod \ 2
[/tex]

? (where I have changed the variable names to help reduce the risk of you confusing yourself)
 
  • #3
Ok, I got it, thanks
 

FAQ: Number Theory with modular arithmetic

What is modular arithmetic?

Modular arithmetic is a type of arithmetic that deals with integers and their remainders when divided by a fixed integer. It is often used in number theory to study the properties of integers and their relationships with each other.

What is a modular equation?

A modular equation is an equation that involves modular arithmetic. It typically has the form of x ≡ a (mod m), where x is the variable, a is a constant, and m is the modulus.

Why is modular arithmetic useful in number theory?

Modular arithmetic is useful in number theory because it allows us to examine the patterns and relationships between integers. It also provides a way to solve problems that involve large numbers or repetitive calculations.

What are some common applications of modular arithmetic?

Some common applications of modular arithmetic include cryptography, computer science, and music theory. In cryptography, modular arithmetic is used to encrypt and decrypt messages. In computer science, it is used to perform operations on binary numbers. In music theory, it is used to understand the relationships between musical notes.

How is modular arithmetic related to prime numbers?

Modular arithmetic is closely related to prime numbers because it can help identify patterns and relationships between them. For example, the Fermat's Little Theorem states that if p is a prime number, then a^(p-1) ≡ 1 (mod p) for any integer a. This theorem is often used to test for primality of large numbers.

Back
Top