Introduction To Number Theory – Richard Michael Hill

Example. We’ll find an approximate value of √ 2 using the Newton– Raphson method. To do this, we regard √ 2 as a root of the polynomial f(X) = X2 −2. We’ll begin with the number a0 = 1, which is fairly close to √ 2, and then calculate the next few terms of the sequence an. Note that we have an+1 = an −a2 n −2 2an = an 2 + 1 an . The next few terms are: a1 = 1 2 + 1 1 = 3 2 = 1.5, a2 = 3 4 + 2 3 = 17 12 ≈1.416667, a3 = 17 24 + 12 17 = 577 488 ≈1.41421568, a4 = 577 976 + 488 577 = 665857 470832 ≈1.41421356237469.

These estimates are fairly good, as the value of √ 2 (up to 14 decimal places) is 1.41421356237310. The sequence an converges very rapidly to √ 2; the number of accurate significant figures roughly doubles with each iteration. This process can be automated on sage as follows var(’X’) f=X^2-2 f.newton_raphson(5,1) [1.50000000000000, 1.41666666666667, 1.41421568627451, 1.41421356237469, 1.41421356237310] Introduction to Number Theory The first two lines of code introduce a new symbol X and define R to be the ring of polynomials over R in the variable X.

If we’d like the approximations given as rational numbers, then we must change the second line to R.=QQ[X], which sets R = Q[X] instead of R[X]. Solving congruences by the Newton–Raphson method. A method similar to the Newton–Raphson method allows us to solve congruences. Suppose we have a polynomial f with integer coefficients, and we’d like to find a solution to the congruence f(x) ≡0 mod pN, where pN is a large power of a prime number p. We can try the following: (1) Find an integer a0 such that f(a0) ≡0 mod pr, where r is a small number (we can think of a0 as an “approximate root”).

(2) Recursively define a sequence of rational numbers an by the Newton– Raphson formula an+1 = an −f(an) f ′(an). It often happens that for n sufficiently large, f(an) ≡0 mod pN. The main result of this section is Hensel’s Lemma, which is a criterion for this method to work. Before describing the theory, we’ll give an example. Example. Let f(X) = X2 + 2 and let p = 3. This means we are trying to find a square root of −2 modulo 3N.

We begin by choosing an approximate root a0 = 1. Note that f(a0) = 12 + 2 ≡0 mod 3, so a0 is a root of f modulo 3. The recursive formula for the sequence an is an+1 = an −a2 n + 2 2an = an 2 −1 an .

The Essential Textbooks in Mathematics explores the most important topics in Mathematics that undergraduate students in Pure and Applied Mathematics are expected to be familiar with. Written by senior academics as well lecturers recognised for their teaching skills, they offer in around 200 to 250 pages a precise, introductory approach to advanced mathematical theories and concepts in pure and applied subjects (e.g.

Probability Theory, Statistics, Computational Methods, etc.). Their lively style, focused scope and pedagogical material make them ideal learning tools at a very affordable price. Published: Introduction to Number Theory by Richard Michael Hill (University College London, UK) A Friendly Approach to Functional Analysis by Amol Sasane (London School of Economics, UK) A Sequential Introduction to Real Analysis by J M Speight (University of Leeds, UK) Published by World Scientific Publishing Europe Ltd.

57 Shelton Street, Covent Garden, London WC2H 9HE Head office: 5 Toh Tuck Link, Singapore 596224 USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601 Library of Congress Cataloging-in-Publication Data Names: Hill, Richard Michael, author. Title: Introduction to number theory / by Richard Michael Hill (University College London, UK). Other titles: Number theory Description: New Jersey : World Scientific, 2018. | Series: Essential textbooks in mathematics | Textbook, with answers to some exercises. | Includes bibliographical references. Identifiers: LCCN 2017044674| ISBN 9781786344717 (hc : alk.

paper) | ISBN 9781786344892 (pbk : alk. paper) Subjects: LCSH: Number theory–Textbooks. Classification: LCC QA241 .H4845 2018 | DDC 512.7–dc23 LC record available at https://lccn.loc.gov/2017044674 British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library. Copyright © 2018 by World Scientific Publishing Europe Ltd. All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the Publisher.

For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher.

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.

Book Information

• Unique ID: cb572a3703dedb9a
• File Extension: .pdf
• File Size: 2,825,961 bytes (2.695 MB)
• Title: –
• Author: Unknown
• ISBN: 9781786344717, 9781786344892
• Pages: 263
• Language: English (en)

Reading & Word Statistics

• Estimated Reading Time: 452.46 minutes
• Total Words: 90,492
• Total Characters: 430,399
• Average Words per Page: 344.08
• Average Characters per Page: 1636.5

Most Frequent Words

mod (1164), modulo (496), number (420), let (330), prime (311), therefore (291), since (286), ring (283), show (271), theorem (247), factor (244), equation (229), numbers (224), quadratic (221), integer (214), we’ll (213), solutions (207), exercise (199), example (198), polynomial (196), solution (195), element (194), theory (192), elements (192), polynomials (191), integers (188), lemma (186), follows (180), irreducible (171), proof (169), implies (168), root (168), congruence (157), see (150), exp (147), suppose (146), log (143), following (140), introduction (136), primes (132), hence (130), case (129), first (129), one (129), two (128), series (127), find (127), factorization (125), calculate (124), using (122), multiple (120), power (119), also (116), primitive (116), unique (115), p-adic (115), common (112), order (112), every (112), use (110), field (109), assume (108), many (106), sequence (106), rings (105), proposition (105), get (104), remainder (104), hcf (100), prove (99), congruences (98), degree (96), note (96), coprime (95), shows (94), odd (94), however (93), real (89), form (89), method (88), congruent (88), roots (85), factors (84), congruency (82), norm (79), positive (77), coefficients (77), group (75), algorithm (73), check (73), gives (71), second (70), equations (70), invertible (69), particular (69), write (69), fact (69), class (68), called (67), either (66).

PDF Download