Modular Arithmetic and Diophantine Equations

  • Context: Undergrad 
  • Thread starter Thread starter drewfstr314
  • Start date Start date
  • Tags Tags
    Arithmetic
Click For Summary
SUMMARY

The discussion centers on solving the modular equation 4k ≡ 1 (mod n) where n is an even integer. It establishes that an inverse of 4 modulo n exists only if the greatest common divisor (gcd) of 4 and n is 2, which implies n is even but not a multiple of 4. Consequently, since 4k is even and 1 (mod n) is odd, there are no solutions for k in this scenario. The conclusion is that the original equation lacks a valid k under the specified conditions.

PREREQUISITES
  • Understanding of modular arithmetic
  • Familiarity with Diophantine equations
  • Knowledge of greatest common divisor (gcd) concepts
  • Basic algebraic manipulation skills
NEXT STEPS
  • Study the properties of modular inverses in number theory
  • Explore the implications of gcd in modular equations
  • Learn about the Chinese Remainder Theorem
  • Investigate other types of Diophantine equations and their solutions
USEFUL FOR

Mathematicians, computer scientists, and students studying number theory or modular arithmetic who seek to deepen their understanding of modular equations and their solutions.

drewfstr314
Messages
20
Reaction score
0
If one is solving a modular equation:

4k \equiv 1 \: (\text{mod } n)

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

4x - 1 = nc
4x - nc = 1

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
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:​
 

Similar threads

Undergrad Question on Primitive Roots and GCDs
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Determine whether ##125## is a unit in ##\mathbb{Z_471}##
  • · Replies 3 ·
Replies
3
Views
1K
Undergrad Dfns group action & group, written in terms of the other
  • · Replies 26 ·
Replies
26
Views
1K
Undergrad I think I've hit upon a very easy proof of impossibility of quintic
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Modulo and Modulus in math and computer programming
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Congruence Subgroups and Modular Forms Concept Questions
  • · Replies 1 ·
Replies
1
Views
2K
What is the remainder when the following sum is divided by 4?
  • · Replies 7 ·
Replies
7
Views
2K
Derive and Solve the Lane-Emden Equation for a Polytropic Gas Sphere
  • · Replies 6 ·
Replies
6
Views
3K
Graduate Definition of Finite Field: Addition and Multiplication Groups
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Classify the isomorphism of a graph
  • · Replies 3 ·
Replies
3
Views
2K