My Math Forum x^2 congruent to 2 mod 5

 Number Theory Number Theory Math Forum

 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 $x^2\equiv 2 \pmod{5}$ has no solutions? (x is an integer) Any help is appreciated!
 February 9th, 2010, 05:50 PM #2 Global Moderator     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.
 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): $\forall k \in \mathbf{N} \\ (5k)^2\equiv 0 \pmod{5} \\ (5k + 1)^2\equiv 1 \pmod{5} \\ (5k + 2)^2\equiv 4 \pmod{5} \\ (5k + 3)^2\equiv 4 \pmod{5} \\ (5k + 4)^2\equiv 1 \pmod{5} \\$ 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!
February 9th, 2010, 09:01 PM   #4
Global Moderator

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.

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!

 Tags congruent, mod

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post claudiohorvi Number Theory 5 November 25th, 2013 06:15 AM coffee_leaf Number Theory 1 September 2nd, 2012 09:07 PM smslca Number Theory 4 January 28th, 2012 10:21 PM johnny Algebra 8 March 4th, 2011 12:37 AM kenhct Abstract Algebra 1 November 2nd, 2010 11:38 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top