My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
February 9th, 2010, 05:23 PM   #1
Newbie
 
Joined: Sep 2009

Posts: 11
Thanks: 0

x^2 congruent to 2 mod 5

Hi!
I need some help on this problem: How to prove has no solutions? (x is an integer)
Any help is appreciated!
sea_wave is offline  
 
February 9th, 2010, 05:50 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: x^2 congruent to 2 mod 5

Compute the squares mod 5. 4^2 = 1, 3^2 = 4, etc.
CRGreathouse is offline  
February 9th, 2010, 06:52 PM   #3
Newbie
 
Joined: Sep 2009

Posts: 11
Thanks: 0

Re: x^2 congruent to 2 mod 5

Hello, CRGreathouse!
Thank you for your advice. Since all nonnegative integers can be expressed as: 5k, 5k + 1, 5k + 2, 5k + 3, 5k + 4 (k can be any nonnegative integer), I found out something useful (I think):

and have proven it. Thus the sequence looks like 0, 1, 4, 4, 1, 0, 1, 4, 4, 1, 0... and there is no 2. But are there any more convenient ways to solve this problem?
Thank you again!
sea_wave is offline  
February 9th, 2010, 09:01 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: x^2 congruent to 2 mod 5

Quote:
Originally Posted by sea_wave
Thus the sequence looks like 0, 1, 4, 4, 1, 0, 1, 4, 4, 1, 0... and there is no 2. But are there any more convenient ways to solve this problem?
Well, I think that squaring 5 numbers is pretty easy, as far as that goes. But you can save some work by noticing that 4 = -1 (mod 5), and just like in the integers, (-n)^2 = n^2 (mod 5). So you really only need to check 0^2, 1^2, and 2^2.
CRGreathouse is offline  
February 10th, 2010, 11:16 PM   #5
Newbie
 
Joined: Sep 2009

Posts: 11
Thanks: 0

Re: x^2 congruent to 2 mod 5

Quote:
Originally Posted by CRGreathouse
(-n)^2 = n^2 (mod 5). So you really only need to check 0^2, 1^2, and 2^2.
Sorry, but I don't get it... could you explain it a little further?
And are there general ways to determine whether congruences like x^2 = a (mod b) have solutions?
Thanks!
sea_wave is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
congruent, mod



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
h^2 congruent to h mod n claudiohorvi Number Theory 5 November 25th, 2013 06:15 AM
Are they congruent at 0 mod y? coffee_leaf Number Theory 1 September 2nd, 2012 09:07 PM
((my) mod n ) congruent to n-1 smslca Number Theory 4 January 28th, 2012 10:21 PM
Congruent circles johnny Algebra 8 March 4th, 2011 12:37 AM
need help for a proof about congruent, and gcd kenhct Abstract Algebra 1 November 2nd, 2010 11:38 AM





Copyright © 2019 My Math Forum. All rights reserved.