12 x^2 - 7x + 1 = 0 (mod p) has solution for every prime p
in [Math]
|
Prev: blackbody CMBR and why kelvin scale is special Chapt 3 #211; ATOM TOTALITY
Next: Russian Spies ???? This is Hilarious !!!!! Does anyone BELIEVE it ? after 911 Inside JOB and ANTHRAX
From: master1729 on 1 Jul 2010 09:19 Dan Cass wrote : > > On Jun 30, 7:47 am, Bill Dubuque > > <w...(a)nestle.csail.mit.edu> wrote: > > > master1729 <tommy1...(a)gmail.com> wrote: > > > > Bill Dubuque wrote : > > > >> master1729 <tommy1...(a)gmail.com> wrote: > > > >>> john wrote: > > > >>>>ubkeybreaker <pubkeybrea...(a)aol.com> wrote: > > > >>>>>ohn <to1m...(a)yahoo.com>> wrote: > > > > > > >>>>>> Prove that for every prime p the > congruence > > > >>>>>> 12 x^2 - 7x + 1 = 0 (mod p) has > solution. > > > > > > >>>>> Are you sure that your polynomial is > > irreducible?????? > > > > > > >>>> No. It equals (3x - 1)(4x - 1)... > > > > > > >>> thus : (3x - 1)(4x - 1) = 0 mod p > > > >>> with solutions 1/3 mod p ,1/4 mod p ... got > it > > ? > > > > > > >> A set of reduced fractions has this property > > > >> iff the denominators have gcd = 1 > > > > > > > what are you talking about? > > > > > > A set of reduced fractions satisfies: for every > > prime p, > > > one of them exists (mod p) <=> denominators have > > gcd = 1. > > > > > > That generalizes the original problem. > > > > > > > 1/3, 1/4 are some integers mod p. they aren't > > really fractions > > > > > > They are in my statement. Moreover, the subring > of > > Q with denominators > > > coprime to m has a natural image in Z/m. This > can > > be verified directly, > > > or, it is a special case of the *universal* > > property of fraction rings > > > (localizations). So such fraction arithmetic > still > > works fine in Z/m > > > e.g. in Z/7 it remains true that 1/2 + 1/6 = > 2/3, > > i.e. 4 - 1 = 3 > > > Informally: fraction arithmetic is universal - > it > > remains valid in > > > every ring it may be interpreted, i.e. where all > > the fractions exist. > > > This basic fact should be taught in every first > > course in abstract algebra > > > but, alas, rarely is that the case. > > > > > > --Bill Dubuque > > > > And here is an amusing result (definitely not > > original with me): > > > > (x^2-2)(x^2-3)(x^2-6) = 0 always has a solution mod > p > > for any prime p. > > > > Hint: Iterated bifurcations in heterococomorphic > > subdomains is not the > > way to do it. > > This follows from the fact that the product of two > non-residues is a residue. > [By residue I mean quadratic residue...] > > That is, if one of 2,3 is a quadratic residue, then > (x^2-2)(x^2-3) = 0 has a solution mod p. > On the other hand if both 2,3 are non-residues, then > 6 is > a residue, so that x^2-6 = 0 has a solution mod p. > > So in any case, (x^2-2)(x^2-3)(x^2-6) = 0 has a > solution mod p. agreed.
From: Bill Dubuque on 1 Jul 2010 14:00 Dan Cass <dcass(a)sjfc.edu> wrote: >mjc <mjcohen(a)acm.org> wrote: >> >> And here is an amusing result (definitely not original with me): >> >> (x^2-2)(x^2-3)(x^2-6) = 0 always has a solution mod p for any prime p. > > This follows from the fact that the product of two non-residues > is a residue. [By residue I mean quadratic residue...] > > That is, if one of 2,3 is a quadratic residue, then > (x^2-2)(x^2-3) = 0 has a solution mod p. > On the other hand if both 2,3 are non-residues, then 6 is > a residue, so that x^2-6 = 0 has a solution mod p. > > So in any case, (x^2-2)(x^2-3)(x^2-6) = 0 has a solution mod p. In fact there are algorithms known for the general case, e.g. see Berend, Daniel; Bilu, Yuri. 96h:11107 11R09 (11R45 11U05) Polynomials with roots modulo every integer. Proc. Amer. Math. Soc. 124 (1996), no. 6, 1663--1671. Motivated by study of the two-variable Diophantine equation P(x) = n!, where P(x) in Z[x] [D. Berend and C. F. Osgood, J. Number Theory 42 (1992), no. 2, 189-193; MR 93e:11016], the authors study the problem of deciding, for a given P(x) in Z[x], whether it has a solution P(x) == 0 (mod m) for every m >= 1. The decision procedure for this question exists as a special case of (complicated) general decision procedures of J. Ax [Ann. of Math. (2) 85 (1967), 161-183; MR 35 #126] and of M. D. Fried and G. S. Sacerdote [Ann. of Math. (2) 104 (1976), no. 2, 203-233; MR 58 #10722]. The authors give simple, necessary and sufficient conditions for P(x) == 0 (mod m) to have a solution for all m, of the type P(x) == 0 (mod m) is solvable for a finite set of m explicitly depending on P(x). More precisely, these conditions are that P(x) == 0 (mod p) is solvable for each prime p <= 2D^A, where D is a product of discriminants over Q of the irreducible factors h_i(x) of P(x) (to suitable powers), and A is an absolute constant, and that P(x) == 0 (mod \D) is solvable, where \D is a product of resultants of the irreducible factors h_i(x), multiplied by the leading coefficients of h_i(x) to suitable powers. By assuming the generalized Riemann hypothesis, the bound D^A can be decreased to c (log D)^2 for an absolute constant c > 0. The authors re-prove a result of V. Schulze [J. Reine Angew. Math. 253 (1972), 175-185; MR 45 #8640; J. Reine Angew. Math. 256 (1972), 153-162; MR 47 #178] that the set of primes p for which f(x) == 0 (mod p) is solvable has a density that is rational, and give a formula for it in terms of the structure of the Galois group of the splitting field of P(x). In addition to Galois theory, the proofs use an effective version of the Chebotarev density theorem, from the reviewer and A. M. Odlyzko [in Algebraic number fields: L -functions and Galois properties, 409-464, Academic Press, London, 1977; MR 56 #5506]. Reviewed by J. C. Lagarias
From: master1729 on 1 Jul 2010 12:30 Bill Dubuque wrote : > Dan Cass <dcass(a)sjfc.edu> wrote: > >mjc <mjcohen(a)acm.org> wrote: > >> > >> And here is an amusing result (definitely not > original with me): > >> > >> (x^2-2)(x^2-3)(x^2-6) = 0 always has a solution > mod p for any prime p. > > > > This follows from the fact that the product of two > non-residues > > is a residue. [By residue I mean quadratic > residue...] > > > > That is, if one of 2,3 is a quadratic residue, then > > (x^2-2)(x^2-3) = 0 has a solution mod p. > > On the other hand if both 2,3 are non-residues, > then 6 is > > a residue, so that x^2-6 = 0 has a solution mod p. > > > > So in any case, (x^2-2)(x^2-3)(x^2-6) = 0 has a > solution mod p. > > In fact there are algorithms known for the general > case, e.g. see > > Berend, Daniel; Bilu, Yuri. 96h:11107 11R09 (11R45 > 11U05) > Polynomials with roots modulo every integer. > Proc. Amer. Math. Soc. 124 (1996), no. 6, 1663--1671. > > Motivated by study of the two-variable Diophantine > equation P(x) = n!, where > P(x) in Z[x] [D. Berend and C. F. Osgood, J. Number > r Theory 42 (1992), no. 2, > 189-193; MR 93e:11016], the authors study the problem > of deciding, for a given > P(x) in Z[x], whether it has a solution P(x) == 0 > 0 (mod m) for every m >= 1. > The decision procedure for this question exists as a > special case of > (complicated) general decision procedures of J. Ax > [Ann. of Math. (2) 85 > (1967), 161-183; MR 35 #126] and of M. D. Fried and > G. S. Sacerdote [Ann. of > Math. (2) 104 (1976), no. 2, 203-233; MR 58 #10722]. > The authors give simple, > necessary and sufficient conditions for P(x) == 0 > (mod m) to have a solution > for all m, of the type P(x) == 0 (mod m) is solvable > for a finite set of m > explicitly depending on P(x). More precisely, these > conditions are that > P(x) == 0 (mod p) is solvable for each prime p <= > = 2D^A, where D is a product > of discriminants over Q of the irreducible factors > h_i(x) of P(x) (to > suitable powers), and A is an absolute constant, > and that P(x) == 0 (mod \D) > is solvable, where \D is a product of resultants of > the irreducible factors > h_i(x), multiplied by the leading coefficients of > f h_i(x) to suitable powers. > By assuming the generalized Riemann hypothesis, the > bound D^A can be decreased > to c (log D)^2 for an absolute constant c > 0. The > authors re-prove a result > of V. Schulze [J. Reine Angew. Math. 253 (1972), > 175-185; MR 45 #8640; > J. Reine Angew. Math. 256 (1972), 153-162; MR 47 > #178] that the set of primes > p for which f(x) == 0 (mod p) is solvable has a > a density that is rational, > and give a formula for it in terms of the structure > of the Galois group of the > splitting field of P(x). In addition to Galois > theory, the proofs use an > effective version of the Chebotarev density theorem, > from the reviewer and > A. M. Odlyzko [in Algebraic number fields: L > -functions and Galois properties, > 409-464, Academic Press, London, 1977; MR 56 #5506]. > Reviewed by J. C. Lagarias that is intresting. as general as the OP could wish for. tommy1729
From: cbrown on 2 Jul 2010 01:15
On Jul 1, 9:32 am, Dan Cass <dc...(a)sjfc.edu> wrote: > > On Jun 30, 7:47 am, Bill Dubuque > > <w...(a)nestle.csail.mit.edu> wrote: > > > master1729 <tommy1...(a)gmail.com> wrote: > > > > Bill Dubuque wrote : > > > >> master1729 <tommy1...(a)gmail.com> wrote: > > > >>> john wrote: > > > >>>>ubkeybreaker <pubkeybrea...(a)aol.com> wrote: > > > >>>>>ohn <to1m...(a)yahoo.com>> wrote: > > > > >>>>>> Prove that for every prime p the congruence > > > >>>>>> 12 x^2 - 7x + 1 = 0 (mod p) has solution. > > > > >>>>> Are you sure that your polynomial is > > irreducible?????? > > > > >>>> No. It equals (3x - 1)(4x - 1)... > > > > >>> thus : (3x - 1)(4x - 1) = 0 mod p > > > >>> with solutions 1/3 mod p ,1/4 mod p ... got it > > ? > > > > >> A set of reduced fractions has this property > > > >> iff the denominators have gcd = 1 > > > > > what are you talking about? > > > > A set of reduced fractions satisfies: for every > > prime p, > > > one of them exists (mod p) <=> denominators have > > gcd = 1. > > > > That generalizes the original problem. > > > > > 1/3, 1/4 are some integers mod p. they aren't > > really fractions > > > > They are in my statement. Moreover, the subring of > > Q with denominators > > > coprime to m has a natural image in Z/m. This can > > be verified directly, > > > or, it is a special case of the *universal* > > property of fraction rings > > > (localizations). So such fraction arithmetic still > > works fine in Z/m > > > e.g. in Z/7 it remains true that 1/2 + 1/6 = 2/3, > > i.e. 4 - 1 = 3 > > > Informally: fraction arithmetic is universal - it > > remains valid in > > > every ring it may be interpreted, i.e. where all > > the fractions exist. > > > This basic fact should be taught in every first > > course in abstract algebra > > > but, alas, rarely is that the case. > > > > --Bill Dubuque > > > And here is an amusing result (definitely not > > original with me): > > > (x^2-2)(x^2-3)(x^2-6) = 0 always has a solution mod p > > for any prime p. > > > Hint: Iterated bifurcations in heterococomorphic > > subdomains is not the > > way to do it. > > This follows from the fact that the product of two non-residues is a residue. > [By residue I mean quadratic residue...] > It wasn't immediately obvious to me why so... It's trivially true for p = 2. For odd p, the multiplicative group of Z_p is cyclically generated by some element g. So an element x is a residue iff x = g^n and n even; and that gives us a normal subgroup of index 2. Your observation follows. Cheers - Chas |