Pub
.
Ma
.
UAB
Vol
.
29
Ns
1
Ab il
1985
ON
CERTAIN
ALGORITHMS
IN
THE
PRACTICEOF
GEOMETRY
ANDTHE
THEORY
OF
NUMBERS
0
.
In oduc ion
Pe e Hil on
and
Jean
Pede sen
[4e
demons a ed
in
111
and
131
a
sys ema ic
me hod
o
olding
a
s aigh s ip
o
nape ,
by wha we called
a
pn-címaxc
bold¿nq
p coceduke,

o
app oxima e,
o
any
desi ed
deg ee
o
accu acy,
a
egula con exs-gon
and
ce ain egula s a
s-gons,
p o ided
ha

s
E
F,
he
se
o
6o1d¡nq
numbm
.

He e
is
de inéd
o be
he
se
o
all
in ege s
s
o
he
o m
2x
x
1
,
whe e
x
>
1,
y
>
2
.
2_1
O
cou se,
suchnumbe s
s
a eodd
.
By
in oducincT
SecokLdaxq
olds
on
he
s ipo
pape
we
showed
how
i
is
possible
o
app oxima e
egula
2
k
s-gons,
whe
e

s
E
F
and

k
>
1

(and
we
included,
o he
sake
o
comple
eness,
he

exac

cons uc ions
o
he
egula

2
k
-gons,
k
>2)
.
The
only
emaining
numbe s
>
3
a e
hose
o
he
o m
2
k
a,

whe e
a
is
odd,

:
P
1

and

no

a
olding
numbe
and

k
>
0
.
Howe e ,
he
me hod
o
app oxima ing
hose egula polygons
can
be
desc ibed
by
a
seguence
o
s eps
as
ollows
(consul
[ll
o
de ails)
.
Fi s ,
sincewe know
ha ,
o any
odd
numbe
a,
2(D(a)
=
1
mod
a,
whe e
i(a)
is
he
Eule
o ien unc ion,
i
ollows
ha
a
is
a
ac o
o
some
elemen
o
F,
say
s,
wi h
s
=
a£
.
We
canuse he
p ima y olding
p ocedu e
o
ob-
ain
a
s ip
o
pape
sui able
o
app oxima ing
a egula
s-gon
.
I
we
hen
in oduce
k'
seconda y
old
lines
a
each
poin ha
would
ha ebeen
a
e ex
o
he
egula
s-gon,
we,
canuse
a
longe
s ip
o
his
olded
ape
o
cons uc
a
egu-
la
2
k
s-áon
.
We
hen
glue his
2
k
s-gon
o
a
pieceo pape
and
old
on
he
lines
connec ina
e e y
9 h
e ex
o
p oduce
he
desi ed
2
k
a-gon
.
In
[2]
and
[3],
we
in oduced
an
al-
go i hm
o
inding
he
op imal
sEF
such
ha
als
.
In
summa y,
he
abo e
p ocedu es
(using
p ima y
andse-
conda y
olds)
p o ided
us,
in
conjunc ion
wi h
he
algo i hm
e e ed
o
abo e,
wi h
a
sys ema ic
me hod ha could
be
used
o
app oxima e egula
con ex
s-gons
o
all
s
%
3
.
The
same
p ocedu es
p oduced
many egula

S ax

s-gons,
whe e

s
E
F
.

In
ac ,
as
discussed
and
p o edin
[2),
o
a
gi en
s
=
(x,y)
E
F,

he
exac numbe
o
s a
s-gons
p oduced
by
he
p ima y olding
p ocedu e
is
2
4'(y)xy
.
Fu he ,
hesecould
be explici ly
desc ibed
.
In
[2]
we aised
he
ques ion
as o
whe he
by
gene a-
lizing
in
a na u al
way he
p ima y
olding,
we migh
be
able
o
a oid
he
gluings ep
desc ibed
abo e,
and
also
be able
o
old
a,Pl
egula
s a
polygons
.
In
his
pape
we
answe
ha
ques ion,
in
he
a i ma i e
.
Gi en

a,b
odd
wi h

a
<2
and
a
p ime
o
b,

we
des-
c ibe
in
Sec ion
1 a
genena í
.zed
p ima y
olding
p ocedu e
which
app oxima es
a
egula
s a
{a}-gon
.
The e
a e,
hen,
e y
ob iousseconda y
p ocedu es
whichallow
us
o emo e
he
es-
ic ion
ha bo h
a
and
b
be
odd
.
Thegene aliza ion
con-
sis s
in
allowinga p ocedu e
o a bi a y
pe iodici y
.
The
p ó-
cedu es
in
p e ious
pape s
ha e
all
been
o
pe iod
1
o
2
.
An
in e es ing
aspec
o
he
con en
o
his
pape ,
and
he
o he pape swe e e
o,
is
he
way
he
geome y
mo i a es
he
numbe
heo y,
and he
subsequen in e ac ion
be ween
he
wo
opics
.
Indeed,
al houqh
he

Quabí-Onde c
Theonem

o
Sec ion
2
would
s and
on
i s
own
me i s
as an
in e es ingpieceo
num-
be
heo y,
i
is
ha d
o
imagine
howone
would
ha e
disco e ed
i
wi hou
he
geome ic
mo i a ion
.
Mo eo e ,
al hough
ou
ge-
ne alized
p ima y
olding
p ocedu e
ob ia es
he
need o glue
a
cons uc ed
N-qon
o
a
oieceo pape
in
o de
o
cons uc
an
M-gon,
wi h
MIN,
he
numbe
heo y
gene a ed
by
he
gluing
echnique,
desc ibed
in [2l
and
[3],
s ands
in
i s
own
igh ,
and
is in no
sense
supe seded
by
he
mo e
sophis ica ed
pape - olding
p ocedu eso
his
a icles,
no
subsumed
in
he
numbe heo y ha
a ises
om
hose
mo e
sophis ica ed
p ocedu
es
.
In
Sec ion
1
we
desc ibe
he
pace - oldingp ocedu e
which
enables
us o
cons uc
a bi a y
s a
polygons
.
We
ha e
sough ,
by including
his
sec ion,
o
make
he
en i e
pape
ea
sonablysel -con ained, hough
we
a eno
ac ually
ad oca ing
he
neglec
o
ou
ea lie pape son
his
subjec
.
Sec ion
2
openswi h
he
de ini ion
o
a
symbol
bal a
2
k1k
2
a
k
which
may
be ega ded
as
encoding
he
ins uc ions
o
olding
a
s ino ape
o
o m
a
s a
{á}
-qon,
wi h
ai
,b
odd,
and
i
a
l
< 2
.

The
"code"
is
desc ibed
in
a ypical
case
in
Sec ion
1
and, in
gene al,
in
Appendix
1
(Sec ion
4)
.
Howe e ,
his
sym-
bol
also
cons i u es
an
in e es ing
algo i hm
o
de e mining
he
quad i-ohdelc
o
2
mod
b,
ha
is,
he
smalles posi i ein e
ge

4

such
ha

2
2
=
l
mod
b
.

Indeed,

i

a
l
is
p ime
o
b,
hen
he
quasi-o de
is
k = 1 k
i
and he
pa i yo
k

i=1
de e mines
whe he
2
=
1
o
2k
-
-1
.
O
cou se,
he
quasi-o de ,
ein o ced
wi h
he
in o ma ion
p o ided
by
he
pa i y
o
,
p o idesmuchmo e
in o ma ion
han
he
o de
o
2
mod
b
.
Examples
a e
gi en
in
Appendix
2
(Sec ion
5)
o
show
how
o
apply
he
algo i hm
o
ob ain
he
symbol
(0
.1)
and
hen how,
in
a
gi en
case,
o
ob ain,
om
he
symbol,
he
ac o
complemen a y
o
b
in
2
k
± 1
.
In
Sec ion
2
we desc ibe
he
symbols,
p o e
some
basic
D ope ies,
and
enuncia e
he
Quasi-O de
Theo em
.
The
heo em
is
p o ed
in
Sec ion
3,
whe e
we
also
ob ain
some
e inemen s
o
he
heo em
o u he
numbe - heo e ical
in e es
.
We
e-
ma k ha an
independen
p oo
o
he
Quasi-O de
Theo em
was
shown
o us
by Ge ald
P es on
.
This
p oo
was
based
on
he
no-
ion
o
Hasse
unc ions
(see,
o
example,
[41)
;
howe e ,
he
di ec ion
o p oo does
no
ake
us h ough
Theo em
2
.5,
which
has
an
immedia e
applica ion
o
pape - olding
.
The
pape closeswi h
he wo
appendices
al eady e e-
ed
o
;
in
he
i s we go back
o
he
geome ical
signi ican-
ce o
he
symbols,and,
in
he
second,
we
discuss,
as
examples,
Fe ma
and
Me senne
non-p imes
.
A
ea u e
o
he
ea lie
pape s
[2]
and
[31
missing
om
he
p esen
pape
was
he
aene aliza ion om
'base
2'
--
he
onlybase
o
geome ical
in e es ,
since
we
modes ly
con
ine
ou sel es
o

b
.ihec
:ng

angles
-- o
'base
'
,

whe e

is an
a bi a y
posi i ein ege
*
1
.
I
appea s ha
his
gene aliza ion
leads
o
in e es ing
di icul ieswhenwe
y
o
in oduce
he
analogs
o
ou
symbols
in
base
,
since,
in
his
gene al
con ex ,
hey
may
ail
o
exis
o
a
gi en
b
.
We
p opose
o
de o e
a
sequel
[61
o
he
s udy
o
gene alized
symbols
and
he
(gene alized)
quasi-o de
p oblem
.
1
.
How
o
old
egula
s a
polycTons
Fi s
we suppose ha
app op ia e
bold,
o
cAe"e,

lines
ha e
beenmade
on
ou
s aigh
s ipo
pape
and
we des-
c ibe
he
ac ual
cons uc ion
n ocess
o
oldinga {a}-gon
l
,
whe e
a
and
b
a e
mu uallyp imein ege swi h
a<b
.
SuoDose,
as
illus a ed
in
Figu e
1,
ha
we
ha e
a
s aigh
s ip
o
pape
ha
has
c easesalongs aigh
lines
emana ing
omma ked
e ices
Ai,i=0,1,
. .
.,
a
he
opand
bo om
ed-
ges,
and
ha ,
o
a
ixed
k,
hose
a
he
pa icula
e ices
A
nk,
n=0,1,2,
. . . .
b,

which
a e
on
he
op
edge,

o miden ical
angles
b
.
Suppose
u he
ha
hese e ices
a e
equally
spaced
(we
desc ibebelow
howyou
migh
ob ainsuch
a
s ip)
.
Figu e
1
(a)
shows
he
beginning
o
he
s ip
.
I
we
old his
s ipon AnkAnk+2
(as
shown
in
Figu e
1(b))
and
hen
on
AnkAnk+l

(as
shown
in
Figu e
1(c)),

he
di ec ion
o
he
op
edge
o
he
apewillbe
o a ed
h ough
an
angleo
2(b
i )
and
he
ane
will
be o ien ed
he
same way,
wi h
espec
o
he
cen e
o
he
polygon
being
delinea ed
by
i s
op
edge
.
We
call
hese
wo
olds
h ough
A
nk,
in
ha
o de ,
a
2(b
)- iuíA
a
A
nkl
and
obse e
ha ,
i
a
2(b
)- wis
is
pe o med
a
A
nk
o
n =
0,
1, 2,
.
.
.,
b-1,
he op
edgeo
he
ape will
ha e
u ned
h ough
an
angle
o
2aw
and he
poin
A
bk
will
hen
be
coinciden
wi h
A
o
.
Thus
he op
edge
o
he
ape
will
ha e
isi ed
e e y
a
h
e ex
o
a
bounding
egula
con-
ex
b-gon,
and
hence
de e mines
a
egula s a la}-gon
.
1
A
closedsequenceo
b
edges ha
isi ,
in
o de ,
e e y
a
h e ex
(mod
b)
o
a bounding egula
con ex b-gon
.
We
include
he
egula
con ex

b-gon
as
he
special
case

a
=1
.
36
Fígu e
i
A
k l~
a,
A
ik+)
.
We
now
explain
how
we ob ained
he
desi ed
c ease
lines
in
he
s ip
o
ape
in
he
i s place
.
Recall
ha we
a e
seeking
o
cons uc a
s a
{e}-gonwhe e
a,
b
a e
mu ually
p imeposi i e
in ege s
wi h

a
<
2
.

We
assume
i s
ha
a,
b
a e
odd
.
Thuswe wish
o
ha e
a
s ip
o
pape
on
which
he
angle
b
u
appea s
a
egula
in e als
along
he
op
edge
.
We
designa e
he
di ec ion
om le
o
igh
as
he
4oAmAd
di ec ion
on
he
ape
.
We
beginby
ma kinga
poin
A
o
on
he
op
o
he
ape
and
making
an
.íní íal
c ease
line
going
in
he
downwa d
o wa d
di ec ion
om
A
o
o'
A
1
a
he
bo om
o
ape,
and
abz(une
ha
he
angle
i
makes
wi h
he
op
edge
is
a

we
call
his
he

pu a í e
angle
.
The
we
con inue
o
b
3
7
o m
new
c easelines
acco ding
o
he
ollowing
ou
ules
:
(1)
The
i s
new
c ease
lineemana es om
he
e ex
A
1
.
(2)
Each
new
c ease
line goes
in
he
o wa d
di ec ion
along
he
s ip
o
pape
.
(3)
Each
new
c ease
line
always
bí6ec 6
he
angle
be -
ween
he
las
c ease
line
and
he
edge
o
he
ape
om
which
i
emana es
.
(4)
The
bisec ion
o
angles
a
any
e ex
con inues
un il
a
c ease
line
p oduces
a
pu a i eangle
o
he
o m
b

whe e
a'
is an
odd
numbe
;
hen
he
olding
s ops
a
ha
e ex
and
commences
a
he
in e sec ion
poin
o
ha
las
c ease
linewi h
he
o he
side
o
he
ape
.
Le
us
conside
he
exampleb
=
11,
a =
3
.
Then
we
cansee
ha
i
we
begin
wi h
an
angle
o
11
a
Ao
(as
shown
in
Figu e
2(a))
and
adhe e
o
he
abo e uleswe will
ob ain
a
s ipo apewi h
he
angles
and
c eases
(do ed
li-
nes)
indica ed
in
Figu e
2(b)
.
Adhe ing
o
he
no a ion
o
he
p ima y
oldingp ocedu es
in
[11,
[21
and
[31, we
could
w i e
his
mo e
gene alized
olding
p ocedu e
as
As
be o e,
his
no a ion
means
ha
i
we begin olding
on
he
s ip
o
pape a
he
placewhe e
he e
is
one
c ease
line slo-
ping
upwaAdb
hen
he
i s
d
l
e e s
o
he
one
bisec ion
(p oducing
a
line
in
a downwa d
di ec ion)
a
A
l0n
( o
an
=
0,1,2,
.
.
.)
on
he op
o
he
ape
;
he
u
3
e e s
o
3
8
{d
1
u
3
d
1u1
d
3
u
1
}

.

(1
.1)
he
3
bisec ions
(p oducing
c eases
in an
upwa d
di ec ion)
ma-
de a
he
bo om
o
he
ape
h ough
AlOn+l
;
e c
.
Howe e ,
he
oldingp ocess
is
duplíca ed
hal way
h ough,
so i
su ices
o
w i e
jus
he
i s h ee
exponen s
in
(1 .1)
.
In
ac ,
we
can
deno e
(1
.1)
e enmo e
simply
as
{1,3,1}

(1
.2)
wi h
he
unde s andina
ha
we
old
dk
luk2
d
k3
u
k4
. .
.
wi h
he
k
i
,
k
2
,
k
3
, . . .
cycling,
in
o de ,
epea edly
h ough
he
alues
1, 3, 1,
. . .
We
call
(1
.1)
o
(1
.2)
a
oA
pe ú
.od
3
.
No e
ha ,
in
his
p ocedu eswe ha e
hi he o
conside ed
o
pe iod
1
({d
n
u
n
})
_a
b
p ima y
oldingp ocedu e
e minology,
he
p ima y olding
in
11,
2,
3]
we e
all
o
pe iod
2

(Id
m
u
n
},
m
*
n)
.
I is
easy
o
see
ha ,
s a ing
wi h
any
pu a i e
angle
a
<
z),

we
will
alwaysob ain
(a,
b
odd,
mu ually
p ime,
by
ou
ules
a
p ima y
oldina
'p oduces'
his
pu a i e
angle
a i e
angle
11
angle
11
n
a
indeed,
ou
c ease
lines
could
ha ebeen
used
o
old
a
s a
11
{
3}
-gon,
heycould
also ha e been
used
o
old
a
11-gon
and
a
s a

{
5}-L}This
ea u e
o
ou
wi h
i s
c easelines
ob iously
applies
in
gene al
:
o he
b-gons
will
be
a ailable
o us
om
he
ape
yielding
he
p ocedu e k
1 ,k
2
.
.
.,k
which
angle
.
We
alsono e
ha ,
s a ingwi h
he
11
n
a
he op
o
he
ape,
we
p oduced
a
pu-
i
a
he
bo on
o
he
ape,
hen
a
pu a i e
he
op
o
he
ape,
and
so
on
.
Thus
i ,
con ex
ape
u nished
s a
s a
a
<
2,

he e
is
always
a
comple ely
de e mined
unique
symbol
like
he
one
abo e
(we
do
no
need
a,b
ela i ely
p ime)
.
App op ia ely
in e p e ed,
we
can
use
his
symbol
o
ead
o
he
oldingp ocedu e
ha
p oduces
he
angle
o

a
along
b
he op
edaeo
he
ape,
so
ha
a
symbol
such
(1
.3)
encodes
a
olding
p ocedu e
o
p oducinga
s a {á}-gon,
and
also
ells
us
wha o he
s a
polygons
we
can
ob ain
om
he
same ape
(o
cou se,
o
each
symbol
a
diag am
simila o Figu e
6
can
be
d awn
o
illus a e
he
ela i e
posi ions
o
he
angles
an
)
b
Be o ewe close hissec ionwe
would
like
o
poin
ou
ha
he
oldingp ocess
desc ibed
abo e
is
he
mob
e6bící
.en
one
possible
.
Tha
is,
he e
could
no
be
any
olding
p ocedu e
ia^
s a
oY
h
.i
.s
ype ha
wouiü
p ocu e
.11G
cÑ, +~-
,
' ed
a
u
u

o
iy
7
on
s
wi_ h
-
. . . . .
.
ewe
olds
.
I is
also
op imal
om
he
poin
o
iew
o
"di -
icul yo execu ion",
o
i
keeAs
he
numbe
o
bisec ionsa
each
e ex
o
a minimum
.
These
las
commen s
a e
explained
as
ollows
.
I
he
olding
p ocedu e
{kl,k2#
. .
.0k }
p oduces
he
angle

,
hen
(see
(2
.3)
and
(2
.4)
bl
2
k
±1,
whe e
b
k = E k
.
I
we adop
he
p ocedu es
desc ibed
in
his sec-
i=1
i
ion
we
willha e
a
p ocedu e

{£l,
92
,....
Qs}

such ha
s
R
=

E

Q
.

is
he

smaUu

numbe

m

such ha

bl
2
m
±l,
j=1
ha
is,
he
quo-6í-ondeA
o
2
mod
b
.
Mo eo e ,
willbe
a mul ipleo
.
s
and,
sui ably
cycling
he
Qj
,
each
k
i
is
a mul iple
o
2
1
.
46
All
hese ac s
a e
con ained
in
henumbe - heo e ical

esul s
o
he
nex
wo
sec ions
.
2
.
S
-
~ n
bols
a
nd
he
quasi-o de
o
2
mod
b
By
he
symbol
b
a
l
a
2
. . .
a
k
l
k
2
. . .
k
b =

a
l +

2
k
ia
i+l
,

i
=

1,
2,

.
we
unde s and
ha
b
is
an
odd
posi i e
in ege ,
ha
a
l
is
an
odd
posi i e
in ege
<
2,
i
=
1,2,
.
.
.,
,

and
ha
k
l ,k21
. .
.k
a e
posi i e
in ege s
such
ha
'
,

a
+1

=

a
l
.

(2
.2)
Le
us
aa ee
whe e
con enien , o
de ine
al
o
all
in ege s
i
by
making a
l
pe iodic
in
i,
wi h
pe iod
,
and
simila -
ly
o
k
i
.
We no e
ha ,
gi en
odd
posi i ein ege s
a,
b
wi h

a
<
2,

he e
is
always
a
symbol
(2
.1)
wi h

a
l = a,

and
ha
he
symbol
is
uniqueup o
.í ~on
;
he ewe
say
ha
(2
.1)
a ises
by
i e a ion
i
he e
exis s
si
such ha
a
l+s
=
a
i'
ki+s
=k
i
'
o
all
i
.
A
p ope
i e a ion,
ha
is,
one
in
which
s
~
,

is
called
a

hepe c don
.
Gi en
b,kl,
.
.
.,k ,
he
equa ions
(2
.2)
ha euniquesolu-
ions,
in
he
"unknowns"
a
.,
namely
i
Ba
i =
bA
i
,
i
=
1,
2,
. .
.,
,

(2
.3)
whe e

B

=

2
k
-

(-1)
,

k

=

E

ki
,

(2
.4)
i=1
and

A
.=2
1
'
-k
i-1
-2k-ki-l-kl-2+
. .
.+(-1) 2ki-(
-
1)
i

i=1,2,
. .
.,
.
(2
.5)
We
no e,
o
u u e
use,
ha
A
i
¿s
índependen
oj
ki
_
l
.
We
also
ema k
ha
he
solu ions
(2
.3)
o
he
equa ions
(2
.2)
alwaysexis ,
bu
ha
( o
a
gi en
odd
posi i e
in ege
b)
he
numbe s
al
gi en
by
(2
.3)
may
ail
o
be
in ege s
.
Howe e ,
we
ha e
immedia ely
P oposi ion
2
.1

(i)

The
6olu c
:ou ob
(2
.2)
a ce
na íonal
numbM

al
sa ís1yíng

0
<
a
l<2
;
(ii)
íñ
any
a
l
.í
.6
an
¡ n egeh,
hen
aie
al
ah
.e
odd
.ín e
.geA6
.
P oo
(i)
I
is
clea
o m
(2
.4)
and
(2
.5)
ha
B,
A
i
a e
odd
posi i ein ege s
.
Thus
om
(2
.3),
each
a
l
is
a
posi i e
a ionalnumbe
.
Now
2k¡ai+l
=
b - a
l
<
b,

since
a
l
>
0
.
Since

al+1

is
posi i e
and

k
i
>
1,

we in e
ha

a
l+1
<
2'
ki-1
To p o e
(ii),
obse e
ha
a
l-l
= b
-
2

a
.
.
Thus
i
a
l
is
an
in ege ,

ai_1

is an
odd
in ege ,
and he
esul ollows
by
ini e
induc ion
.
48
As an
applica ion,
conside
B,
A
i
,
gi enby
(2
.4),
(2
.5)
.
As
al eadyobse ed,
B
and
A
i
a e
odd
posi i e
in ege s
o all
i
.
Mo eo e ,
i
ollows
immedia ely
om
ki
(2
.3)
ha
he
solu ion
o
he
equa ionsB = x
i+2
x
i+l
,
i
=
1,2,
.
.
. .
,xi+l
=
x
l
,

is

x
i
=
A
i
,

so
ha
k
.
B = A
i + 2
1Ai+
.l
.

(2
.6)
is
a
s mbol
.
Thus,
by
P oposi ion
2
.1,
A
l
A
2
. .
.
A
k
1
k
2
. .
.
k
B
(2
.7)
we will
also
need
he
ollowing
elemen a y
p oposi ions
;
he
i s
is
p o ed
in
[21
.
P oposi ion
2
.2

In
. he
bymbal

(2
.1)
,
gcd
(b,a
i
)

-í .6
Lndependen
Ul 1
.
P oposi ion
2
.3

iñ,
ín
. he
bymbal

(2
.1)
,
ki
>
n,
. hen
al+1
<
ñ
.
2
P oo
This
is
ob ious
om
(2
.2)
.
P oposi ion
2.4

(Pe iodici y
lemma)

11,
.i
.n
(2
.1), heh
.e
exis
. s
an

s

euch ha

s
i

and

k
i+s
-
ki
joh

aP,C

i,

hen

al+s
=
al
dan
aCQ
.

i
.
P oo I
is
clea om
(2
.5)
ha i
ki+s
=ki
o
all
i,
hen Ai+s
-_
Ai
o
all
i
.
The
esul
now
ollows om
(2
.3)
.
The
pe iodici y
lemmaasse s ha
i
he
sequence
k1,k2,
. .
.,k
is
a epea ing
sequence,
hen
he
symbol
(2
.1)
is
ob ainéd
by
he
same
epe i ion
.
I
he e
is
no
p ope epe i
ion,
we
say
ha
he
symbol
(2
.1)
is
neduced
añd
w i e
b
a
l
a
2
k
1
k
2
a
k
(2
.8)
Then
a gene al
symbol
(2
.1)
is
ob ainedby
nepea íng

a
unique
educed
symbol
;
and
a educed
symbol
(2
.8)
is
ob ained
by
compkUsb
.íng
a
gene al
symbol
.
Gi en
posi i e
odd
in ege s
a
wi h
a
<
2,

he e
is
a
unique educed
symbol
(2
.8)
=
a
.
and
b
wi h
We come
now
o
ou
main
p elimina y
esul
.
Theo em
2
.5

Le

k
l,k
2
,.
.
. .
k

be
poeí í e .íníegeu
a
.~í h
E

k
i
= k
>
2
.

Then,
bon
a g
.í en
odd
.ín egeA

al
<
.2

,

we
ha e
i=1
k

ala2
. .
.a

al
a
2
. .
.a
-1
a
2
-1

.í6
and
on y
-í~

2
k+l
-1
k
1k2
.
.
.
.k

k1
k
2
. .
.k
-1
k
+l
in
eí heA
ccue,

la e en
.
P oo Assume
he
le -hand
symbol
.
Then,
by
(2
.3),
I
we e
odd,
we wouldha e
2
k
-lla
i
,
an
e iden
con adic ion
.
Thus
is
e en
and
al =
A
i
,
o
all
i
.
So
(2
k
-

(
-
1)
)a
i
=

(2
k
-

1)A
i
.
Loe
now
sol e
he
equa ions
2k+1
- 1 =
X
i
+
2ki
Xi+l'
whe e

k'
i=k
i
,
1
<-i
-< -1,
k
= k
+
1,

so
ha

E
ki
=k+1
=k',
i=1
sa ,
o
ob ain
(compa e
(2
.6))
x
i
=
A!,
wi h
(compa e
(2
.5))
A1-2k'-k!_

~
.1
-
2k'-k1!_1-k1!_2
+
. .
.+
.
(-1)
2kl

-

(-1)

(2
.9)
Thus
we
ob ain
he
symbol
Howe e ,
we
see
om
(2
.9),
ecalling
ha
Al is
independen
o
k ,
ha
Al
= A
1
=
al
,
es ablishing
he
exis ence
o
he
igh -hand
symbol
o
he
heo em
.
The
con e se
is
p o edsimi-
la ly
.
The e
is
acompanion heo em
as
ollows
;
we need
no gi-
e
an
exnlici
n oo
.
Theo em
2
.5
*

Le

kl,k2,
. . .
,k

be
pos .í i e
ín egeu
wí h
Ek
i
= k
?
1
.

Then,
Son a
gí en
odd
ín egeA

al
<
2k-1,

we
ha e
i=1
A
'
A'
.
. .
A' -
A'
1 2

1
k
l
k
2

...

k
-1

k
+l
2
k
+1
a
l a2
k
l
k
2
. . .
.
.
.
a
k
is
and
o ney
íS
al
a2
.
.
a -1
a
2
k+1
+1
kl
k
2
.
.
k
-1
k
+1

In
"eA
case,

.í s
odd
.
Quasi-O de Theo em

Le-

b

be an
odd
pos
.í c
: e
íw egen, and
.le

a
.
i

be an
odd
pos
.í
í e
.ín egen
wí h

a
l< 2

and
a

p~u
:me
xo
b
.
Then í6

b
T4e
p o e
his
heo em
in
he
nex
sec ion
bu
we
may
imme
dia elyanounce
he
ollowing
co olla y,
ela ing
o
he
ohden
o
2
mod
b
.
Co olla y
2
.6

eU
.i h
che
dame
hupo
. hehes
as
ín
. he
9
.ua~sí-Onde
Theo em,
«úe
ha e
(i)

.í~


íz
e en,

hen he
anden
o
6

2
mod
b

.í
s

k

and,
e en
í6

k
.í 5
e en,

2
k/2
P--1
mod
b
;
(ii)

í6


.í6
odd,
hen
he
oAden
o6

2
mod
b

í
s

2k,

and
2
k
-1
mod
b
.
3
.
P oo
o
he
Main
Theo em
p o e
We
a e
now
eady
o
s a e
ou
main
heo em
.
a
l
a
2
. . .
a
k
l
k
2
.
.
.
k
wí h

E k
i
=
k,
we
ha e
i=1
(i)

k

.í,b
- he
m
.Lní
.mal
Q
sueh ha

bi~~±1,
(ii)

b
12
k
-1
,¿~


.í s
e en,

bl2
k+1

í5


.i s
odd
.
We i s s udy
a
special
case
o
he
main
heo em
and
Theo em
3.1

Le

Q
>
2
.

Then
í~

~
-1
we
ha e

E

Qi
i=1
P oo
We
a gue
by
induc i n
on
Q
,
he
case
Q
=
2
being
_i
l
ialsince

3
Cl~
.

Thus
we
assume
he
heo em
o

Q
>
2

and
p o e
i
o
Q
+1
.

Le
hypo hesis,
we ha e
2'
-"
-1
I

=1

and

2
1
=l,

he
conclusion
is
i ially
ue
.
I no ,
i
ollows om
he
pe iodici y
lemma
ha ,
o
some

i,
Qi
>
2
.
Wi hou
eal
loss o
gene ali ywe
may
assume
ha
Q
>
2
so
ha ,
by
P oposi ion
2 .3, al
<
2
Q-1
.
Thus,
by
ou
induc i e
A
al
a2
...
as
2
2
-
1
(3
.2)
k1
k
2
...
ks
s
wi h
E
k
i
IQ
.
By
epe i ion,
i
necessa y,
we ind
he
i=1
symbol
a
l a2
...
a
29
-
1(3
.3)
k
1 k2
. . .
k
wi h
Ek
i
=
Q
.
By
Theo em
2
.5
we
deduce
he
symbol
i=1
Pl i e
ki
=
k
i
,
1
-<
i
-<
-1,
k
=k
+1
.

Then
1
E
1
ki
=
Q+1
.
Comp essing,
i
necessa y,
we
ob ain
u
wi h

E
k'
I
(Q+1)
.

By
he
uniqueness
o
he
educed
symbol,
as
i=1
1
a
unc ion
o
b
and
a
o
,
we in e ha
(3
.5)
is
iden ical
wi h
(3
.1),
so ha
he
induc i e
s ep
is
achie ed
and
he
heo
em
is
p o ed
.
The e
is,
o
cou se,
a companion
heo em,
wi h
almos
¡den
ical
p oo ,
namely,

.
Theo em
3 .1
*
Le

Q
>
1
.

Then
we
ha e

E

Q¡

I

Q
.
i=1
11

11

11
a
l
a
2
...
a -1

a
k
1
k
2
...

k
-1

k +l
a
la2
.
.
.
a
2
1
a
a"
.
.
.
all
12

u
k
'
k'
...
k'
1
2

u
2
2
Q
J
P oo
o
he
Quasi-O de
Theo em
Fi s
le
(3
.4)
(3
.5)
Thus,
by
Theo em
3
.1
o
3
.1*,
klk
0 .
wi h
no
es ic ionon gcd(a
l,b)
.
Le

E k
.
= k
and
le
k

be
he
minimal
Q
such ha
1=1
1

k

0
bl2
Q
± 1
.

I
2
0
± 1
=
bq,

hen,
ob iously,
k

a
l
q a
2
q
.
. .
a q
2
0
±1
Now
suppose ha
a
l is
p ime o
b
.
Then,
by
(2
.3)
and
(2
.4),
(2k
-

(_,)
)a
¡
=
bAl
.
Since
b
is
p ime
o
ai
,
we ha e
bl2
k
- (-1)
.
Since
klk
0
,
he
minimali y
o
k
0
implies
ha
k = k
0
.
Mo eo e
i is
plain
ha
bl2
k
-1 i
is
e en
and
bl2
k
+1
i
is
odd
.
Rema ks
.
(i)
No e
ha
we ha ep o ed
ha ,
i
we emo e om
he
hypo heseso
he
Quasi-O de
Theo em
he
condi ion
ha
al
be
p ime
o
b,
and
i
k
is
dejíned
as
he
minimal
Q
Q

such
ha
bl2
±
1,
hen

E k
i
¡k
.
I we
w i e
quo(b)
o
i=1
he
cguasi-o de
o
,?
.
mod
b,
hen
his says
ha
i
a
la2
. . .
a

b

I
,
hen
E
kil
áuo(b)
.
Mo eo e ,
he
k
l
k
2
. . .
k
i=1
.immedc
:a eey
ansla able
in o
old- heo e ic
language!
Fo
i
ells
us
ha ,
i
we know
how
o
old
ou
s ipo
pape
o
p o
k

k+1
duce
a
s a

{
2 a l
}-gon, hen,
o p oduce
a
s a

{2

a
-1}-gon,
we
in oduce
one
mo e old
line
p ecisely
a
hose e ices
on
he op
edgeo
he
ape
which
a e
des ined o become e ices
o
ou
polygon
.
5
.
Appendix
2
:
á
ew
we
ll-chosen
examples
whe e,
by
(2
.5)
We no e
ha ,
i
I
al
a
2
...
a
b
wi h
a
l
=
1,
hen,
by
(2
.3),
2
k -
(
-1)
=
bAl,
A

=

20
-1

-

Z
a -2

+

.
1
J
Ek
.
=k,
i=1
1
(5 .2)
wi h

a
.
=

E k
.
.

(5
.3)
i=1
1
Mo eo e ,
by
ou
main
heo em,
k
=
quo
(b)
.
Le
us
apply
his o
case
b =
641
.
We
ob ain,
by
ou
algo i hm,

641
[15
159 241
25 77
141 125
129
72 1 4 3 2 2 2 9
Thus
we
in e ,
since
k
= 32,
=
9,
ha
and,
om
(5
.2)
auo(641)
= 32
and,
indeed,
ha

232 + 1
=-
-
0
mod641
.
Mo eo e ,
we
know om
(5
.1)
2
32
+ 1
=
641Al,
(5
.4)
A
1=
2
23
-
2
21
+ 219 - 217 + 214
-
2
10
+29 - 27 +1
=
6700417
.
This
is,
o
cou se,
Eule 's
amous
ac o iza ion
showing
5
ha
22 + 1 is
no
a
(Fe ma )
p ime
.
4
Only
he
pape - olding
ana ic
would
ake
he
iew
ha
he
p incipalin e es
o
(5
.4)
is
ha
i
shows
how
o
old
he
egula con ex
641-gon
andce
ain
s a
641-gons
.
As
a
second
example,
conside
he
symbol
23
He e
k =
11,
=
6,
so
ha
1
11
3
5 9 7
1
2
21 1
4
4
See,
o
example,
he
on co e
o
[5]
.
quo(23)
=
11,
2
11
- 1

0
mod
23,
and,
againby
(5
.2),
he
complemen a y
ac o
is
Re e ences
Rebu
el
16
d'oc ubne
de¡
1984
Depa men
o
Ma hema ics
Uni e si y
o
San aCla a
San aCla a
Cali o nia
95053
U
.S .A
.
A1 =
27
-
2
6
+25-23 +
2
- 1
=
89
Thus
2
11
-
1
=
23
"
89
and
is
no
a
(Me senne)
P ime
.
[1]
Pe e
Hil on
andand
JeanPede sen,"App oxima ing
any
egu
la
polygonby olding
pape
:
An
in e play
o geome y,
ana
lysis_andnumbe
heo y",
Ma hema ics
Magazine,
Vol
.
56
.
Nó
3,
1983
(141
-
155)
.
[2]
-------------------------,
"Regula
polygons,
s a
polygons
and
numbe
heo y",
Coxe e
Fes sch i
,
Ma h
.
Sem
.
Giessen
164,
1984,
(217
-
244)
.
[3]
-------------------------,
"Folding
egula
s a
polygons
an l ni

ymbe
heo %T"
The
Ma hema ical
In ell
i
a
en
c
e
.
Vol
.
7
(1),
1985
(15
-
26)
.
[4]
K
.R
.
Ma hews
and
A
.M
.
Wa s,
"A
gene aliza ion
o
Hasse's
gene aliza ion
o
he
Sy acuse
algo i hm",
Ac a
A i hme ica
XLIII,
1983
(75
- 83)
.
[5]
Ma hema
ical
In elligence
,
Vol
.
6
.
Ns
3,
1984,
on co e
.
[6]
Pe e
Hil on
and
Jean
Pede sen,
"On
gene alized
symbols,
o_
de s
and
quasi-o de s"
( o
appea )
.