Modular Arithmetic and Diophantine Equations

  • Thread starter drewfstr314
  • Start date
  • Tags
    Arithmetic
In summary, the conversation discusses solving a modular equation 4k ≡ 1 (mod n) with n being even and known. It is mentioned that in order to solve for k, one needs to find the inverse of 4 modulo n. However, it is also pointed out that this only has solutions if (4,n) = 2 (n is even, but not a multiple of 4) and does not divide 1, meaning there is no inverse of 4 modulo n. The conversation ends with confirming that there is no k that satisfies the original equation.
  • #1
drewfstr314
20
0
If one is solving a modular equation:

[itex]4k \equiv 1 \: (\text{mod } n)[/itex]

with n even, known, for k, then one needs to find the inverse of 4 modulo n:

[itex] 4x - 1 = nc [/itex]
[itex] 4x - nc = 1 [/itex]

But this only has solutions iif (4,n) = 2 (n is even, but not a multiple of 4), which doesn't divide 1, so there is no inverse of 4 modulo n. Does this mean that there isn't a k that satisfies the original equation?

Thanks!
 
Physics news on Phys.org
  • #2
hi drewfstr314! :smile:

that's right :smile:

4k is even, and 1 (mod n) is odd (since n is even), so there's no solution …

what is worrying you about that? :confused:​
 

1. What is modular arithmetic?

Modular arithmetic is a mathematical system that deals with integers and their remainders when divided by a fixed number. It is often used to solve problems involving periodic phenomena, such as time or repeating patterns.

2. How is modular arithmetic different from regular arithmetic?

In modular arithmetic, there is a fixed number called the modulus that all calculations are based on. This means that the result of any operation will always be within the range of 0 to the modulus. Additionally, in modular arithmetic, adding and multiplying by the same number multiple times may result in a different answer compared to regular arithmetic.

3. What are Diophantine equations?

Diophantine equations are polynomial equations where the solutions must be integers. They are named after the ancient Greek mathematician Diophantus who studied and wrote about them extensively.

4. How are modular arithmetic and Diophantine equations related?

Modular arithmetic is often used to solve Diophantine equations, as the solutions must be integers and modular arithmetic deals with integers and their remainders. By converting the equation into a modular form, it is often easier to find solutions.

5. What are some real-world applications of modular arithmetic and Diophantine equations?

Modular arithmetic and Diophantine equations have various applications in fields such as cryptography, computer science, and physics. For example, they are used in creating secure encryption algorithms, optimizing computer algorithms, and solving problems related to periodic phenomena in physics and engineering.

Similar threads

I Question on Primitive Roots and GCDs
    • Linear and Abstract Algebra
Replies
2
Views
793
I Modulo and Modulus in math and computer programming
    • General Math
Replies
5
Views
2K
A Modular forms, dimension and basis confusion, weight mod 1
    • Linear and Abstract Algebra
Replies
12
Views
1K
What is the remainder when the following sum is divided by 4?
    • Precalculus Mathematics Homework Help
Replies
7
Views
1K
I Congruence Subgroups and Modular Forms Concept Questions
    • Linear and Abstract Algebra
Replies
1
Views
1K
Solve the simultaneous congruence modulo equation
    • Calculus and Beyond Homework Help
Replies
3
Views
1K
I Classify the isomorphism of a graph
    • General Math
Replies
3
Views
1K
B Is it invalid to redefine the sgn function in this way in a proof?
    • Linear and Abstract Algebra
Replies
15
Views
4K
A Structure of modulo-integer matrix group GL(r,Z(n))?
    • Linear and Abstract Algebra
Replies
17
Views
4K
A Anti-dual numbers and what are their properties?
    • Linear and Abstract Algebra
Replies
1
Views
921

Hot Threads

Recent Insights

Back
Top