Turn on thread page Beta
    • Thread Starter
    Offline

    0
    ReputationRep:
    find all integer x in the range 1\leq x \leq 100 which satisfy x^2 \equiv -2 (mod 17)

    i can find all the x's just by plugging in the values in the range of 1 to 100, but i wanna know how to do this using the modular arithmetic.
    thanks!
    Offline

    15
    ReputationRep:
    (Original post by singedang2)
    find all integer x in the range 1\leq x \leq 100 which satisfy x^2 \equiv -2 (mod 17)

    i can find all the x's just by plugging in the values in the range of 1 to 100, but i wanna know how to do this using the modular arithmetic.
    thanks!
    If -2 is a quadratic residue there will be a solution in 0<x<9. Then -x is also a solution. And all other solutions will be of the form x+17k, 17k-x.
    • Thread Starter
    Offline

    0
    ReputationRep:
    (Original post by RichE)
    If -2 is a quadratic residue there will be a solution in 0<x<9.
    i don't understand what this means...
    (Original post by RichE)
    Then -x is also a solution.
    and how does the one above implies this?
    (Original post by RichE)
    And all other solutions will be of the form x+17k, 17k-x.
    and how did you come up with this equation?
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (Original post by singedang2)
    and how does the one above implies this?
    x^2 = (-x)^2.
    Offline

    15
    ReputationRep:
    (Original post by singedang2)
    i don't understand what this means...
    google "quadratic residue" or look it up in a text

    and how does the one above implies this?
    what GB said.

    and how did you come up with this equation?
    because addition and multiplication are well-defined in modular arithmetic.

    Sorry, no more help tonight, having run out of metaphorical toilet paper :p:
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (Original post by singedang2)
    i don't understand what this means...
    I don't either. I tried the good old-fashioned method of googling but found nothing useful. :p: I have a feeling that 17/2 = 8.5 (rounded up to 9), as well as (-x)^2 = x^2, has something to do with it.

    (Edit: http://mathworld.wolfram.com/QuadraticResidue.html explains quite nicely.)

    (Original post by singedang2)
    and how did you come up with this equation?
    If x is a solution, then x + 17 is a solution, x + 2*17 is a solution, x + 3*17 is a solution... same with -x.
    • Thread Starter
    Offline

    0
    ReputationRep:
    (Original post by generalebriety)
    If x is a solution, then x + 17 is a solution, x + 2*17 is a solution, x + 3*17 is a solution... same with -x.
    i understand that. but i'm really interested in how that equation came up.
    Offline

    15
    ReputationRep:
    (Original post by singedang2)
    i understand that. but i'm really interested in how that equation came up.
    what equation? :confused:

    x+17k = x mod 17

    and squaring is well-defined in mod arithmetic: i.e.

    if y = z mod 17 then y^2 = z^2 mod 17
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: October 13, 2006

University open days

  • University of Bradford
    All faculties Undergraduate
    Wed, 21 Nov '18
  • Buckinghamshire New University
    All Faculties Postgraduate
    Wed, 21 Nov '18
  • Heriot-Watt University
    All Schools Postgraduate
    Wed, 21 Nov '18
Poll
Black Friday: Yay or Nay?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Equations

Best calculators for A level Maths

Tips on which model to get

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.