How Can You Find 'y' When ((m*y) mod n) ≡ (n-1)?

  • Context: Undergrad 
  • Thread starter Thread starter smslca
  • Start date Start date
Click For Summary
SUMMARY

The discussion focuses on finding the value of 'y' such that the equation ((m*y) mod n) ≡ (n-1) holds true, where m is defined as the floor of the square root of n. It is established that if m is a divisor of n, no solution exists. The key takeaway is that a solution for 'y' can be found using the Extended Euclidean Algorithm, but only when m and n are coprime, meaning GCD(m, n) must equal 1.

PREREQUISITES
  • Understanding of modular arithmetic
  • Familiarity with the Extended Euclidean Algorithm
  • Knowledge of greatest common divisor (GCD)
  • Basic concepts of congruences
NEXT STEPS
  • Study the Extended Euclidean Algorithm in detail
  • Explore properties of coprime numbers and their implications in modular arithmetic
  • Practice solving congruences with various values of m and n
  • Review examples of modular equations and their solutions
USEFUL FOR

Mathematicians, computer scientists, and students studying number theory or cryptography who are interested in solving modular equations and understanding congruences.

smslca
Messages
63
Reaction score
0
If given a 'n' value and m = floor ( squareroot(n) )
then is there any way to find the value of 'y' , such that

((m*y) mod n) is congruent to (n-1)
 
Physics news on Phys.org
with the help of a friend
i figured out that, if m is the divisor of n, it won't be possible to get a solution .
But what about the other values?
 
Hi, smsica,
you are looking for a solution to the congruencymy \equiv -1 \pmod nThe definition of congruency says that two numbers are congruent to n when their difference is a multiple of n; so solving this congruency can be expressed as finding integers y,k such thatmy+1 = nkornk-my = 1Call z = -y, and look for solutions k,z tonk+mz = 1You do that using the Extended Euclidean Algorithm; you will find that a solution can only be found when m and n are coprime, that is, when GCD(m,n)=1.

There is a simpler example here (with numbers whose GCD is larger than 1, but the mechanics of the algorithm are the same):
http://www.mast.queensu.ca/~math418/m418oh/m418oh04.pdf
 

Similar threads

Undergrad Proof for subgroup -- How prove it is a subgroup of Z^m?
  • · Replies 11 ·
Replies
11
Views
3K
Undergrad Dfns group action & group, written in terms of the other
  • · Replies 26 ·
Replies
26
Views
1K
Undergrad Trouble with a passage in Zariski & Samuel's Commutative algebra text
  • · Replies 5 ·
Replies
5
Views
1K
Undergrad Why is the dual of Z^n again Z^n ?
  • · Replies 13 ·
Replies
13
Views
2K
Undergrad Can integers be defined as N[[sqrt(1)]]?
  • · Replies 25 ·
Replies
25
Views
2K
MHB How Can We Find the Minimum 2-Norm of Ax-y Using an Orthogonal Matrix?
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Matrix rank in terms of determinant polynomial
  • · Replies 14 ·
Replies
14
Views
4K
Can Natural Numbers m and n Satisfy x + 1/m < y - 1/n?
  • · Replies 22 ·
Replies
22
Views
1K
Undergrad Can one find a matrix that's 'unique' to a collection of eigenvectors?
  • · Replies 33 ·
2
Replies
33
Views
2K
Express ##x^3+y^3## in terms of ##m## and ##n##
  • · Replies 17 ·
Replies
17
Views
3K