Vol. 10, No. 4, 2017

Download this article
Download this article For screen
For printing
Recent Issues

Volume 11, 1 issue

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
New algorithms for modular inversion and representation by the form $x^2 + 3xy + y^2$

Christina Doran, Shen Lu and Barry R. Smith

Vol. 10 (2017), No. 4, 541–554
Abstract

We observe structure in the sequences of quotients and remainders of the Euclidean algorithm with two families of inputs. Analyzing the remainders, we obtain new algorithms for computing modular inverses and representing prime numbers by the binary quadratic form x2 + 3xy + y2 . The Euclidean algorithm is commenced with inputs from one of the families, and the first remainder less than a predetermined size produces the modular inverse or representation.

Keywords
number theory, continued fraction, binary quadratic form, algorithm
Mathematical Subject Classification 2010
Primary: 11A05
Milestones
Received: 10 September 2013
Revised: 6 May 2015
Accepted: 11 July 2016
Published: 7 March 2017

Communicated by Filip Saidak
Authors
Christina Doran
Lebanon Valley College
101 College Ave.
Annville, PA 17003
United States
Shen Lu
Lebanon Valley College
101 College Ave.
Annville, PA 17003
United States
Barry R. Smith
Lebanon Valley College
101 College Ave.
Annville, PA 17003
United States