Re: number theory with congruence.


"Arturo Magidin" <magidin@xxxxxxxxxxxxxxxxx> wrote in message
news:eb879m$2qfj$1@xxxxxxxxxxxxxxxxxxxxx
In article <eb8609$ecd$1@xxxxxxxxxxxxxxxx>,
mina_world <mina_world@xxxxxxxxxxx> wrote:
hello sir~

x^2 + x + 7 = 0 (mod 3^3)

----------------------------------------
i know the algorithm in this case (mod p^n).

so,
let f(x) = x^2 + x + 7.

f(x) = x^2 + x + 7 = 0 (mod 3)
=> x^2 + x + 1 = 0 (mod 3)
=> x= 1 (mod 3)
=> x = 1 + 3t (t in Z)

Okay...


f(1+3t) = f(1) + f'(1)*3t = 0 (mod 3^2)

Note that in this case,

f'(x) = 2x + 1

so

f'(1) = 2+1 = 0 (mod 3), hence the solution is singular. It is not so
easy to lift in this case. You will find that f(1+3t) = f(1) (mod 3^2)
for all integers t; hence the single root will either not lift, or
lifts to multiple (in this case, 3) roots mod 3^2. This happens
because Hensel's Lemma does not apply.

Here, f(1) = 0 (mod 9), so all three lifts of the solution modulo 3
will lift to a solution modulo 3^2.

since f(1) = 9 and f'(1) = 3,
=> 9 + 9t = 0 (mod 3^2)

oops...this is not a thing desired.

Not if you want to apply Hensel's Lemma; but you cannot because the
solution is singular.

so, i can't progress any more.
i need your advice.

Each of t = 1, 4, and 7 (mod 9) are solutions modulo 9. Each is a
singular solution, since f'(t) = 0 (mod 3), from which you will obtain
that for each of them, f'(t) = f'(t+3^2*k) (mod 3^3) for every integer
k. Hence, you need to check each of the values 1, 4, and 7 modulo
3^3. If they are roots, then all three values lying above it are roots
modulo 3^3; if they are not, then none of the three values lying above
it are roots.

This process continues with each root at each level it will either
lift to p roots, or not lift. There is a theorem that tells you that
once you get "high enough", then you can always lift the solution up
one level, but of all the lifts, one and only one will lift to "two
levels up", giving you something closer to Hensel's Lemma.

Here is what the theorem says, taken from "An Introduction to the
Theory of Numbers", 5th Edition, by Ivan Niven, H. Zuckerman, and
H. Montgomery, Theorem 2.24, pp. 89:

THEOREM Let f(x) be a polynomial with integer coefficients. Suppose
that f(a) = 0 (mod p^j), and that p^t||f'(a), and that j>= 2t+1. If
b = a (mod p^{j-t}), then f(b) = f(a) (mod p^j), and
p^t||f'(b). Moreover, there is a unique t (modulo p) such that
f(a+tp^{j-t})=0 (mod p^{j+1}).


thank you very much.
and i finded the interesting algorithm.

for reference, http://en.wikipedia.org/wiki/Hensel's_lemma

x^2 + x + 7 = 0 (mod 3^3)

i try...again.
let f(x) = x^2 + x + 7. so, f'(x) = 2x + 1

f(x) = x^2 + x + 7 = 0 (mod 3)
=> x^2 + x + 1 = 0 (mod 3)
=> x= 1 (mod 3)
=> x = 1 + 3t (t in Z)

since f'(1) = 3 = 0 (mod 3) and f(1) = 9 = 0 (mod 3^2),
f(1+3t) = 0 (mod 3^2) for all integers t by Hensel's lemma.
so, the solutions of f(x) = 0 (mod 3^2) is x=1 (mod 3).

because, {x| f(x)= 0 (mod 3^2)} in {x| f(x)= 0 (mod 3)}
because, 3^2 | f(x) => 3 | f(x)

anyway,
since x=1 (mod 3) is x= 1, 4, 7 (mod 9),
the solutions of f(x) = 0 (mod 3^2) is x=1, 4, 7 (mod 9)

1) x = 1 (mod 9)
since x = 1 + 9s and
f'(1) = 3 = 0 (mod 3) and f(1) = 9 =/= 0 (mod 3^3),
so x is not solution of f(x) = 0 (mod 3^3) by Hensel.

2) x = 4 (mod 9)
since x = 4 + 9s and
f'(4) = 9 = 0 (mod 3) and f(4) = 27 = 0 (mod 3^3),
so x = 4 (mod 9) is solution of f(x) = (mod 3^3) by Hensel.

3) x = 7 (mod 9)
since x = 7 + 9s and
f'(7) = 15 = 0 (mod 3) and f(7) = 63 =/= 0 (mod 3^3),
so x is not solution of f(x) = 0 (mod 3^3) by Hensel.

thus, x = 4 (mod 9) is solution of f(x)=0 (mod 3^3).
since x = 4 (mod 9 ) is x = 4, 13, 22 (mod 3^3)
then answer is 4, 13, 22 (mod 3^3).

how do you think about it ?


.

Relevant Pages

  • Re: Lehmer-Schur pseudocode?
    ... the Lehmer-Schur algorithm. ... A Google Groups search shows a single mention in the history of Usenet, ... If anyone can suggest a better algorithm ... choice for finding the roots of a black-box analytic function, ...
    (comp.programming)
  • Re: Mod 2011
    ... and work in the ring of integers modulo q. ... The sequence always starts: ... investigate whether square roots of -1 are in any way relevant. ... I don't see a pattern. ...
    (sci.math)
  • Re: Exact (LISP-ish) calculations in Ruby?
    ... There's an algorithm for calculating square roots, ... not in process) to the algorithm for long division. ... Raphson method) for calculating square/cube/fourth/... ...
    (comp.lang.ruby)
  • Re: Polynomial root-finding
    ... >> Polynomials with extremely high orders, or very closely spaced roots, or very ... Also Euclid's algorithm only seems to ... I'm not sure why you are opposed to deflation. ...
    (sci.math.num-analysis)
  • Re: Doubts about e and n
    ... >>A prime which is small (to make encryption easy) and which is relatively ... It *may* be possible to find cube roots mod n much more ... modulo n1*n2*n3 ... ... and if you use the same e with multiple moduli, ...
    (sci.crypt)