Author |
Topic: b^2 = -1 mod 41 (Read 2270 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Re: b^2 = -1 mod 41
« Reply #1 on: Feb 28th, 2004, 8:23pm » |
 Quote  Modify
|
Wilson!
|
|
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: b^2 = -1 mod 41
« Reply #3 on: Feb 29th, 2004, 8:46am » |
Quote Modify
|
Oh, that's the boring way to show something exists. What if 41 were 47657, or 47659?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: b^2 = -1 mod 41
« Reply #4 on: Feb 29th, 2004, 9:11am » |
Quote Modify
|
on Feb 28th, 2004, 8:23pm, Eigenray wrote:
Very nice, Eigenray! It took me some time to understand why: 41 = 1 mod 4.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: b^2 = -1 mod 41
« Reply #5 on: Feb 29th, 2004, 10:02am » |
Quote Modify
|
I'm still missing something then.
Wilson's Theorem states that iff p is prime, (p-1)!==-1 mod p. For example, 6!=720, and as 7*103=721, it follows that 6!==-1 mod 7.
So using the result here, 40!==-1 mod 41, and as we're solving, b2==-1 mod 41, we need to show that b2==40! mod 41. That is, b2=40!+41k. Hmm?
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: b^2 = -1 mod 41
« Reply #6 on: Feb 29th, 2004, 3:37pm » |
Quote Modify
|
I think the non-boring approach Eigenray had in mind was something like, working mod 41...
By Wilson, 40! = -1
But 40! = 20! * 21 * ... * 40
= 20! * (-20) * ... * (-1)
= 20! * 20! * (-1)^20
= (20!)^2
This argument would fail for 43, or any prime = 3 mod 4.
|
| « Last Edit: Feb 29th, 2004, 3:48pm by NickH » |
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: b^2 = -1 mod 41
« Reply #7 on: Feb 29th, 2004, 4:05pm » |
Quote Modify
|
That is very clever, NickH. Thanks for the explanation.
And it is easy to see why it works for prime bases, p==1 mod 4, but doesn't when p==3 mod 4.
For example, by Wilson's theorem, 42!==-1 mod 43.
However, 42!=21!*22*23*...*42==21!*21*20*19*...*1*(-1)21=-(21!)2 mod 43.
Therefore, 21!2==1 mod 43.
Of course it doesn't prove that b2==-1 mod 43 has no solution, it's just (as NickH pointed out) that the argument fails in this case.
|
| « Last Edit: Feb 29th, 2004, 4:30pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: b^2 = -1 mod 41
« Reply #8 on: Mar 1st, 2004, 4:19am » |
Quote Modify
|
on Feb 29th, 2004, 4:05pm, Sir Col wrote:| Of course it doesn't prove that b2==-1 mod 43 has no solution, it's just (as NickH pointed out) that the argument fails in this case. |
|
In fact, when a prime p = 3 mod 4, there is no such b. This is based on the following statement:
There exists b such that b2 = r mod p iff r(p-1)/2 = 1 mod p.
|
|
IP Logged |
|
|
|
Benoit_Mandelbrot
Junior Member
Almost doesn't count.
Gender:
Posts: 133
|
|
Re: b^2 = -1 mod 41
« Reply #9 on: Mar 1st, 2004, 5:55am » |
Quote Modify
|
How about :: b=i=sqrt(-1) ? Since -1=-1 (mod 41), i should work.::
|
| « Last Edit: Mar 1st, 2004, 5:56am by Benoit_Mandelbrot » |
IP Logged |
Because of modulo, different bases, and significant digits, all numbers equal each other!
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: b^2 = -1 mod 41
« Reply #10 on: Mar 1st, 2004, 6:33am » |
Quote Modify
|
Umm Benoit,
Number theory specifically deals with the properties of whole numbers.
http://mathworld.wolfram.com/NumberTheory.html
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: b^2 = -1 mod 41
« Reply #11 on: Mar 1st, 2004, 7:49am » |
Quote Modify
|
If you can explain what "i mod 41" means, then I'll consider whether or not it's a valid answer. I have no idea how you'd create an analog of imaginary numbers for a finite field.
|
|
IP Logged |
|
|
|
Benoit_Mandelbrot
Junior Member
Almost doesn't count.
Gender:
Posts: 133
|
|
Re: b^2 = -1 mod 41
« Reply #13 on: Mar 1st, 2004, 8:25am » |
Quote Modify
|
Well, using the definition that a mod b =a-b[lfloor]a/b[rfloor], and because [lfloor]xi[rfloor]=[lfloor]x[rfloor]i, i mod 41=i.
This can be expanded to say that ai mod b=i(a mod b).
Also a mod bi=a mod -b, and ai mod bi=i(a mod b).
Now ai mod b=ai mod bi.
Since i2=-1, and -1 is real, then -1=-1, so i2=-1 (mod 41).
Using these definitions, then n mod i=n mod -1. Most calculators I know don't do complex modulo. I had to create my own using the a mod b definition. I have Derive 5, and I checked my work against it's, and it worked.
|
| « Last Edit: Mar 1st, 2004, 8:56am by Benoit_Mandelbrot » |
IP Logged |
Because of modulo, different bases, and significant digits, all numbers equal each other!
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: b^2 = -1 mod 41
« Reply #14 on: Mar 1st, 2004, 8:54am » |
Quote Modify
|
on Mar 1st, 2004, 7:49am, rmsgrey wrote:| If you can explain what "i mod 41" means, then I'll consider whether or not it's a valid answer. I have no idea how you'd create an analog of imaginary numbers for a finite field. |
|
Define the ring { a + bi | a,b [in] [bbf]p} = [bbf]p[ i] = [bbz][ i]/(p[bbz][ i]).
Question: Is this a field?
on Mar 1st, 2004, 4:19am, Barukh wrote:
In fact, when a prime p = 3 mod 4, there is no such b. This is based on the following statement:
There exists b such that b2 = r mod p iff r(p-1)/2 = 1 mod p. |
|
For the case r=-1, we simply note that b4 = 1, so the order of b is either 1,2,4, but it can't be 1 or 2. And the order of b divides the order of the group: 4 | p-1.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: b^2 = -1 mod 41
« Reply #15 on: Mar 1st, 2004, 9:13am » |
Quote Modify
|
Number Theory is awesome!!! Can you guys tell me which is the best book to start from bottom and go in real advanced topics?
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: b^2 = -1 mod 41
« Reply #16 on: Mar 1st, 2004, 9:14am » |
Quote Modify
|
on Mar 1st, 2004, 8:54am, Eigenray wrote:
Define the ring { a + bi | a,b [in] [bbf]p} = [bbf]p[ i] = [bbz][ i]/(p[bbz][ i]).
Question: Is this a field?
|
|
multiplicative identity is obvious, just leaving the question of multiplicative inverses.
(a+bi)(a-bi)=a2+b2, which is real, so has a multiplicative inverse. So (a+bi)-1=(a-bi)(a2+b2)-1
So it looks like it satisfies the field axioms
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: b^2 = -1 mod 41
« Reply #17 on: Mar 1st, 2004, 9:32am » |
Quote Modify
|
on Mar 1st, 2004, 9:14am, rmsgrey wrote:(a+bi)(a-bi)=a2+b2, which is real, so has a multiplicative inverse. So (a+bi)-1=(a-bi)(a2+b2)-1
So it looks like it satisfies the field axioms |
|
What's (9+i)-1 mod 41 then?
For which primes p is {a+bi | a,b [in] [bbf]p} a field?
|
|
IP Logged |
|
|
|
Benoit_Mandelbrot
Junior Member
Almost doesn't count.
Gender:
Posts: 133
|
|
Re: b^2 = -1 mod 41
« Reply #18 on: Mar 1st, 2004, 10:08am » |
Quote Modify
|
(9+i)-1 mod 41=9/82+3361/82*i.
[lfloor]a+bi[rfloor]=[lfloor]a[rfloor]+[lfloor]b[rfloor]i.
I forgot about that identity.
|
| « Last Edit: Mar 1st, 2004, 10:19am by Benoit_Mandelbrot » |
IP Logged |
Because of modulo, different bases, and significant digits, all numbers equal each other!
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: b^2 = -1 mod 41
« Reply #19 on: Mar 1st, 2004, 3:36pm » |
Quote Modify
|
on Mar 1st, 2004, 10:08am, Benoit_Mandelbrot wrote:| (9+i)-1 mod 41=9/82+3361/82*i. |
|
No, because 82-1 [notin] [bbf]41 = [bbz]41. That is, there is no integer x such that 82*x = 1 mod 41.
And since 82 has no inverse, you can't divide by it.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: b^2 = -1 mod 41
« Reply #20 on: Mar 1st, 2004, 4:39pm » |
Quote Modify
|
on Mar 1st, 2004, 6:33am, TenaliRaman wrote:Umm Benoit,
Number theory specifically deals with the properties of whole numbers. |
|
As towr has suggested, and Eigenray is carefully leading into, Number Theory can extend beyond whole numbers. However, unless explicitly stated otherwise, number-theoretic results are assumed by convention to apply only to whole numbers.
on Mar 1st, 2004, 7:49am, rmsgrey wrote:| If you can explain what "i mod 41" means, then I'll consider whether or not it's a valid answer. I have no idea how you'd create an analog of imaginary numbers for a finite field. |
|
The Gaussian integers [bbg] = [bbz] [times] [bbz]i. Divisibility and modularity can be defined on them just as it is among the integers. The norm of gaussian integer z is defined as N(z) = zz* = |z|2. This is chosen over the absolute value since it is an integer. It still satisfies the triangle inequality, and it is obvious that N(wz) = N(w)N(z).
The Euclidean algorithm still holds: for all z, w [in] [bbg], w [ne] 0, there exists unique q, r [in] [bbg] such that z = qw + r and N(r) < N(w). z [equiv] z' mod w if w | (z - z').
The concept of "prime" also holds in the gaussian integers. One important difference: [bbg] has 4 units: 1, -1, i, -i. [bbz] only has two: 1, -1; and we usually ignore -1, restricting our attention to the positives. But such a restriction is not workable for [bbg]. A gaussian is prime if any factorization of it includes a unit. If p is a gaussian prime, then so are -p, pi, -pi. These are called the associates of p. There is a simple test for whether or not a gaussian integer is prime, but since it relates to something Eigenray is pointing towards, I will leave that for now.
The fundamental theorem of Arithmetic still holds for [bbg], but the factorization is only up to associates. (Any prime in a factorization may be replaced with an associate to obtain another factorization. A unit may need to be multiplied by the factorization in order to get the actual number you want, rather than one of its associates).
on Mar 1st, 2004, 8:54am, Eigenray wrote:
Define the ring { a + bi | a,b [in] [bbf]p} = [bbf]p[ i] = [bbz][ i]/(p[bbz][ i]).
Question: Is this a field? |
|
Depends on p, of course, as you indicate:
on Mar 1st, 2004, 9:32am, Eigenray wrote:| For which primes p is {a+bi | a,b [in] [bbf]p} a field? |
|
More generally, for which z in [bbg] is [bbg]z a field? Hint:What is the answer to the same question for regular integers? If you answer that one, it not hard to figure out the answer to Eigenray's.
on Mar 1st, 2004, 9:13am, Sameer wrote:| Number Theory is awesome!!! Can you guys tell me which is the best book to start from bottom and go in real advanced topics? |
|
"An Introduction to the Theory of Numbers" by Niven & Zuckerman used to be a standard, but I don't know if it is still out there.
To get into real advanced topics though, you will also need a good introduction to Abstract Algebra. I'm not sure of what is available here (the book I learned from, I would not suggest for someone learning it by themselves).
on Mar 1st, 2004, 9:14am, rmsgrey wrote:
multiplicative identity is obvious, just leaving the question of multiplicative inverses.
(a+bi)(a-bi)=a2+b2, which is real, so has a multiplicative inverse. So (a+bi)-1=(a-bi)(a2+b2)-1
So it looks like it satisfies the field axioms |
|
As Eigenray indicates in his answer to Benoit_Mandelbrot, you've overlooked something: Just because a2 + b2 has a real multiplicative inverse does not mean that (a-bi)/(a2+b2) lies within [bbf]p.
|
| « Last Edit: Mar 1st, 2004, 4:43pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: b^2 = -1 mod 41
« Reply #21 on: Mar 1st, 2004, 10:20pm » |
Quote Modify
|
Hi guys  For an alternative solution, you can try to solve this problem without using any number theory guns, but rather, just using some beautifully simple group theory facts ... this latter approach is the solution I had in mind. Yes of course there are intersections between number theory and group theory, but namely Wilson's theorem and other number theory theorems like the FLT are not necessary to solve this problem.
|
| « Last Edit: Mar 1st, 2004, 10:23pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: b^2 = -1 mod 41
« Reply #22 on: Mar 1st, 2004, 11:09pm » |
Quote Modify
|
William,
i think NickH earlier gave one of the most simplest solution possible which reqd nothing more than common sense 
Icarus,Eigenray et all,
I am going to blurt out some of my very weak group theory concepts in accordance to the questions asked in this thread so far, so please do correct me if i made some error anywhere ....
The proof that {{a+bi},+,*} is a ring is simple and we can take that for granted.We can go ahead and prove that {{a+bi},*} is commutative knowing that {Z,*} is commutative.So {{a+bi},+,*} is a commutative ring.It also has the same multiplicative identity as Z i.e 1 , so the ring is a commutative ring with unity.
Now i came up with a problem when i was trying to find the multiplicative inverse.
(a+ib)(c+id)=1
implies
c=a/(a^2+b^2) and d=b/(a^2+b^2)
My question is
are we considering a+ib (the gaussian integers)? in which case c+id won't be in our set of {a+ib} which would imply that its not a field
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: b^2 = -1 mod 41
« Reply #23 on: Mar 2nd, 2004, 4:15am » |
Quote Modify
|
on Mar 1st, 2004, 9:32am, Eigenray wrote:| For which primes p is {a+bi | a,b [in] [bbf]p} a field? |
|
For this to be a field, it is needed that for every a, b [in] [bbf]p, there exist c, d [in] [bbf]p such that (a+bi)(c+di) = 1, or ad+bc = 0, ac-bd = 1 simultaneously. From the first equation we get d = a-1bc, and plugging it into the second equation, we get: (a2+b2)c = a.
The last equation has a solution in c iff a2+b2 [ne] 0 mod p for all a, b.
1. Let p = 4k+1, then we know there exists b such that b2 = -1 mod p, so put a = 1.
2. Let p = 4k+3, and assume the existence of a, b such that b2 = -a2 mod p, or (ba-1)2 = -1 mod p. But this cannot be, as we’ve seen before.
Thus, the answer to Eigenray’s question are primes of the form 4k+3.
P.S. After posting this, I realized TenaliRaman did almost the whole thing before. 
|
| « Last Edit: Mar 2nd, 2004, 4:25am by Barukh » |
IP Logged |
|
|
|
Benoit_Mandelbrot
Junior Member
Almost doesn't count.
Gender:
Posts: 133
|
|
Re: b^2 = -1 mod 41
« Reply #24 on: Mar 2nd, 2004, 6:02am » |
Quote Modify
|
So what you're saying is that we can't have non-integer results for a mod b? You can't do 13/3 mod 3/2 ?
|
|
IP Logged |
Because of modulo, different bases, and significant digits, all numbers equal each other!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print