On the Solution of Simultaneous Congruences of a Certain Type

(1)

NII-Electronic Library Service

M]MolRs oF SAGAMI

II(sTlrcTe oT TscEtNoLoGy

Vel.19,Ne,1,1985

On

the

Solution

of

Simultaneous

Congruences

of a

Certain

Type

Akira

K6No

In a commutative fieldof characteristic zero, we have already seen the well-known statement

(e.g.,

Resultant)for findinga solutien of the followingsystem: _(cf.

[1,

S24

and

S30])

{;,::.

X

I-i8

where a., b,EQ and where X isan unknown. In this _paper,we shall introducean investigation

with respect to the followingproblem. -In the above-mentioned system, leta., b,eZ. Then the followingquestien arises: What fieldsof characteristic P

(prime)

possess solutions inthe given system (cf.

S1.

Notations

and

Introduction

Notations

We shall often use the following symbols.

N

set of all natural numbers

Z

set of all rational integers

Zb

or

Z/(P)

residue class

field

(mod,

P)

Q

field

of rational numbers

degf

degree

of

f(X)

maxf

leading

_coeMcient _of

f<X)

minf coethcient of

XO

in

f(X):

i.e.

constant

adj A adjoint of the matrix

A

Z[X]

integral

dornain

of _polynomials _over Z

Zla[X]

integral

domain

of _polynornials over

Zh

O[X]

integral

domain

of polynomials over

Q

(1,

A,･･･,LL,)

ideal

or the _greatest common

[a,

b]npEinPa[batb]

orfi(X)h(X)R(L

g)

terrn

divisor

if

a _principal

least

common multiple of _a _and

b

(eZ)

factorization

into

_prime

factors

PL,

(eN):

le=:1,

2,

･･･, m

prirne

(e

IV)

,.･ an unknown

divisibility

(a

divides

b)

nondivisibility

t proper subset

i

=h(X)f(co, ci, ･･-, ct)

for

h(X)=E c,X`, c,eZ U

h(X)

is

_primitive

resultant of two _polynomials

f(X),

_g(X)

ideal:

_LeZ[X]

*

_igtsecE

_iget

_va"n

₅₉

_e;

₁₀

A 12 Heett

(2)

igec=\it\rapt

ca

19#

en

1e

Introduction

In

S

4

we shall show miscellaneous ways

for

solving simultaneous congruences with

unknowns

X

and

P

as

follows.

(1.1)

where

(1.2)and

where

REMARK

throughout characteristic of all systems.

As

or

f-O

In

(1.3)

lf

degAl1

(1.3)*

g,=llPLkfO

(P).

That

is,we obtain the solution

from

fl(X)iO

(a)

where

PL

iseach value of

P

in the

(1.3)*.

Moreover

we may treat

fl

and _gt such that

(1.4)

minfltO and mingitO.

If

minfl==O and ming, ±

O,

it

follows that

ttm-X,tl.fl)"tTO(p)

where minfl*#O and

lill.

Thus,

from

fl

:X`ifl*!O

(P)

we

have

XEO

(P)

or

fl*i

(cf.

Lemrna

4 in

_S2)

Thus,

i)

when

I

I,tLOo

((Pp)),

the solution

is

XiEO

(B,)

where rning,=llPik=-O

(P).

2)

When

(lil,t;oO(S)

where minfl*#O, mingitOs

thistype

is

the object of our investigation.

(i.e.

the type of

(1.4))

Similarly,

if

minA=O and

if

mingi=O,

we form that

two

n

A(X)=Z

a.X'iO

(mod.

P)

o

m

gi(X)=:Z

b,XsEO

(mod.

P) o

a.

b,ea

degAldeg

gi '

P

isa rational _prime.

O. Henceforth

we shall use the

integral

ccethcients such that a.,

b,eZ

this paper.

These

coeMcients are

interpreted

as the coeMcients

in

the

field

of

P

by

denoting

modulo

P. Therefore,

in

Z[X]

we must treattransformations

we shall see

later,

we may

briefly

f(X)

to

L

and

f(X)!O

(mod.

P)

to

f(X)=O

(P)

(P).

(1.1),

we shall investigatethe case such that

degAll

and

deggill.

and

deg

_g,=O, we can

find

a value

of

P.from

form

(3)

On the Solution

of

SimultaneousCengruences

_of

a Certain1),Pe

A==Mif,*

Igi==XZ2gi*

where minfi* LO, mingt* SO and where

li).1,

l2>=1

.

Obviously,

X!O

(P)

is

the solution

for

every

P

(prime).

Finally,

we must solve that

f,*-O

(P)

I

g,*EO

(P)

where minL'tO, ming,"#O.

(i.e.

the type of

(1,4))

And

also,

in

(1.1)

we treat the

following

coeMcients:

(1.5>

(ao,ai,.･.,a.)=1

and

(bo,bi,-･･,b.)=1.

That is,

_fi

and _gi are _primitive _{polynornials.} If

(ao,

ai,-･･,a.)==atl and

(bo,bi,･･･,b.)=

btl,

(1.1)

is

the form

A(X)=of,(X)iO

(P)

Ig,(X)=bg,(X)iO

(P)

.

This

system

is

solved

in

four

cases as

follows.

(i)

when

lg.=-,O

,(.P,',

X=-u

_(a)

are solutions in

(1.1)

where all teGZ and where

(a,

b)=llPLk.

(ii)

when

{#.tT,}?,t=P8

,.,,

frorn

gi(X)-O

(A)

we can

find

a solution

in

(1.1),

where a=llPik=O

(P).

(iii)

when

{bfni(xO

)(!6

(p),

this

is

solvecl such as

(ii).

(iv)

when{;;[ll:g[S],

･

thiscase

is

the object of our investigation.

(i.e.

the type of

(1.5))

S2.

Pre]iminaries

Here

we exhibit

fundamental

_properties

of the ring, fieldand

integral

dornain

_which

are essential to this paper.

LEMMA

1. Jlf

S

is

an

integral

domain

with an identity element, and

ij'

_the unique

factorizatien

theorem

holds

in

S,

then same theorem

holds

for

the

Polynomial

domain

S[X].

(cf.

[I,

S

26])

LEMMA

2. ILf

a

Polynomial

f(X)

in

S[X]

_.ftxctors

in

K[X],

then

it

factors

in

S[X]

where

S

is

an

integral

domain

with an

identity

element and where

K

is

the _q"otient

field

of

S. (cf.

[I,

S26])

LEMMA

3. Ple'imitive

Polynomials

mtry uniquely

(but

for

unit _.ftzctors)

be

decomPosed

into

_Prime

_factors

which are themselves

Primitive

Polynomials.

(cf.

[I,

S26])

(4)

reec-me V<\ivpt

ce

19 #

ca

1 e

LEMMA

4. in

a .lield

ofcharacteristic

Por

zero,

if

f(X)g(X)=O,

then

flX)=O

or g(X)=O.

(cf.

[I,

g14])

LEMMA

5.

Let

K

be an arbitrat:y

field,

and

tet

f(X)

and _g(X)

be

two

Polynomials

in

K[X].

_ly'

the resultant vanishes, the

Polynomiats

f

and g have either a common

nen-constant _.factor, or the

leading

coofcient vanishes

in

both

of

them, _and _cenversely.

(cf.

[I,

S30])

In

order to understand the ways

in

S4.1,

2,

3

and

4,

we want to

introcluce

a

_general

concept

in

these sections.

That

is,

let

(2.1)

(L

g)={f'Ef+g*g: any

fixed

LgeZ[X]

and all

f*,

g*eZIX]} .

Evidently,

_(L

_g)

is

an

ideal

generared

by

f

and g.

This

ideal,

as

is

well-known,

is

not

always a principal

ideal.

In

thisset

(L

g) we

have

the

following

lemmas.

Of

course,

let

max

#O

_and max _gtO.

As

we shall see

later,

the

lemmas

are essential to the Euclidean

algorithrn and the algorithm

in

A.E.C

(cf.

S4.2

and

S4.3).

LEMMA

6. if

(f;

g)gh and

if

f=O

(P)

and _g=O

(P),

then

h=O

(P).

Proof:

This

is

trivial.

LEMMA

7. in

(2.1)

there exist

h's

such that

degh=O

if

and enly

if

R(f; g) eO.

Proof:

See

[I,

S30]

or

(5.1)

in this _paper.

LEMMA

8. in

Z(X),

let

fl

and _gi

be

Primitive

Po(ynomiais.

11hen,

thay

have

the

gyeatest common

divisor

h*

such that

degh*)1

_if

and only

ij

R(fl,gt)=O

where

h'

is

Primitive.

Proof:

This

isclear

from

Lernma

1,

2,

3,

5

and

Z[X]cQ[X].

LEMMA

9. in

Z[X],

if

a.L=q.g.+h.,

then

(L,

g.)2(g.

h.)

where a.,f;,g.,q.,

h.GZ[X].

Proof:

Let

(g.,

h.)eGg.+Hh.

where al]

G,

HeZ[X].

From

the

assumption

Ggr+flhr=HizrL+(G-H4r)gr

･

Hence,

this

is

clear.

LEMMA

10. I)2

a.L+b.g.=X`'h.,

ij'

h.=O,

then

_g-,IL where

l.).l

and wlaere a.eZ;

b.,L,

g.eZ[X]; a."LO,

degL)1,

degglll.

Proof:

From

h.=O,

a,L=-b.g.

follows.

Hence,

this

is

clear,

LEMMA

11.

in

Z[X],

let

A,(X)f<X)+B,(X)g(X)=h,(X) and

A,(X)f<X)+B,(X)g(X)=

h,(X).

-44-NII-ElectronicMbrary

lt

(5)

On theSolution

_of

_{SimultaneousCongruences}_oj'aCertain71vPe

ijA,(t),

_A,(t),

B,(t)

_B,(t)$O

(mod.

P)and

I21[li:oo(mod.P),

then{flt)g(t)=-o

_(mod.

-O P) where tGZ.

Proof:

By

the well-known theorem of the

linear

algebra,

(i.e.

in

homogeneous

linear

equations,

if

the number of equations

is

equal to the nurnber of unknowns, a necessary and

surncient condition

for

solutions other than xt=x2=･･･=x.==O

is

thatthe

determinant

of the

coethcients

be

zero), this isclear.

{

_;F/llltg

LEMMA

(mod.

12.

_p)

in

Z[Xl,

are

_{impiied in}

i.f

<f;

g)Dhi(X),soiutionsh2(X),

of

thethen

_systeml

the

That

is,

PerhaPs

there are extraneo"s roots.

sotutions

of

the

_system

h,(t)!O

(mod.

P).

h,(t)-O

Proof

minant

in:

By

Lemma

11 is11, this is clear. zero or non-zero.That

is,cosiderthat thevalue ofthe

deter-S3.Fundamentaltheorems

When

sertion

inwe

findthe solution of

{1.1)

by

three theorems as

follows.

waysin

S4,

weshallfinallyarrlve at an

as-THEOREM1.

in

thesystem

A(X)..

Igi(X)io

(p)o

(p),

let

X-u

(P)

where

P

is

an unhnown and where zaisthe

fenown

tnteger.

(1)

When

fl(u)

#:O er g,(u)#O and when

(fl(a),

_{g,(u))=llPL",}

X=-u

(a)

is

_the solution

in the_system, where every

ll.

(2)

When

fl(u)=O

and _&(u)=O, X=-u

(a)

are the solutions in the _system,where

R,'s

are all

Primes.

Proof:

(1)

clear.

(2>

This

is

FremA(u)iO

(P)

and

trivial.

g,(u)Eo

(P),

nPLk!!O(P)

holds.Hence

this is

THEOREM2.

in

thesystem

A(X).

Ig,(X)iO

(fl)O

(R)

where

a

isthe knewn

_Prime,

tet X!u,

and the laterresPectively. 11fuiiu2(Ilt),(4)thenand

Xi!!u2

X- u,

(Fl)(a)

beis

thethe

sotution

of

the

former

solution in the _system.

Proof:

This

is

evident.

(6)

-45-NII-Electronic Library Service

Mec=kJit\rept

ca

19

#

ee

1 g

THEoREM

3. Let

h(X)iO

(P)

be

only one

form

zvith respect to ttvozanlenotvns

X

and

P

where

degh(X)ll.

(1)

if

h(t)#O

and

if

h(t)=llIZtk,

then

X=-t

(ll)

is

a solution in the

form

where some

teZ.

(2)

lf

h(t)=O,

then

X=-t

(R,)

are selutions

in

this

form

where

a's

are all

Primes

where some teZ.

Proof:

(1)

Since

h(t);O

and

h(t)=-O

(P),

llP£k=O

(P)

holds.

Hence

this

is

clear.

(2)

From

PIO

for

every P

(prime),

this

is

clear.

CoRoLLARy.

lf

degh(X)ll

and

if

h(X)!!O

(P)

is

only one empression with respect to

two unlenowns

X

and

R

then the number

of

selutions

in

thiseopression

is

infinite.

Proof:

When

(1)

in

Theorem

3.

For r such that

h(ti)=h(tE)=･.･=h(t,)==c

(constant),

it follows that rS.degh, because

an n-th degree _polynomial

(i.e.

h(t)-c=O) distinct from zero has at most n roots in any

integral

domain.

(cf.

[1,

S24])

Hence

this isobvious,

When

(2)

in

Theorem

3. This

istrivial.

REMARK

1.'

The

following

rules are convenient

for

us.

(Rule

1)

In

(1.1),

if

(minl,

ming,)=1, then

XfO

(P).

Proof:

When

X-O

(P),

this isabsurd.

(Rule

2) If XEf(X)EO

(P),

f(X)GZ[X],

leN

and XXO

(P),

then

_f<X)iO

_(P).

Proof:

This istrivial from Lemma 4.

S4.

Various

ways

for

finding

solutions

in

(1.1)

1.

Using

Sylvester's method elimination

(or

Resultant)

Let R(fl,g,)

be

the resultant of

fl(X)

and _g,(X) in

(1.1)

with

(1.2),

(1.3),

(1.4)

and

(1.5).

(4.1)

(In

allblank anan-1 ...'''''''''''' an an-1... anan-1... R(fl, gi)=

bmbm-i''''''''''''''''

bm

bm-p･-..''..'

bmbm""i･'''-'''''

spaces we

have

to substitute zeros.)

-46-... ao ...ao i - - - -- - - - --...ao ...be ...bo i---...bo m n

(cf.

(4.19))

(7)

On the Sotution

of

SimultaneousCongruences

of

a Certain llyPe

Of

course,

let

maxfl==a.

#O

_and _maxgi=b.;O

in

(1.1).

Evidently,

_the _order of the

deter-minant R(A, _g,)ism+n.

From

the well-known _procedure, it

follows

that

(4.2)

A*fl+gi"gi

=:R(A, gi)

where

fl*,

_g,*eZ[X].

(cf.

(5.1>

or

[1,

S301)

Hence,

from

Lemma

6 R(fl,

g,)EO

(P).

Here,

in

order to find the solution in

(1.1)

we have two cases as

follows.

Case 1: When R<fl,g,) iEO,

frorn

R(A,g,)=O

<P)

we can

find

a value of P.

That

is,

letR(fl,g,)==llPZk.

By _putting P to

₄

we have

fl(X)iO

(Il)

and _{gi(X)iO(Il,).}

Hence,

from Theorem 2 in

_g3

we can obtain the solution

in

(1.1).

REMARK

2. As

above mentioned,

in

Theorem

2 (S3)

it

is

_generally

dithcult

that we

find

the solution in the system

A(X)i!O

(a)

Ig,(x)!o

(a).

However,

Z[X]

is

interpreted

by

ZP.[X]

frorn

RemarkO.

Then,

Zb,[X]

is

a _principal

ideal

ring.

Hence,

using

Euclidean

algorithm we can

find

the greatest common

diviser

h*(Elt･,[X])

of

fl(X),

g,(X)

(eZ.,[X])

from

R(A, g,)=O

(mod.

Il,).

(cf.

[II])

Then,

we may _proceed in an even simpler manner.

Case

2:

When

R(fl,g,)=O. we can treat as

follows.

From

Lemma

8,

if

R(fl,g,)==O,

then

(4.3)

h"(X)lfl(X)

and

h"(X)lg,(X)

where

h(X)=h(X),

degh*)1

and where

h*

is

the _greatest comrnon

divisor

of

A

and _gi.

As

we shall see

later,

a method

for

actually

forming

h*(X)

is

treated

in

S4.2

or

S4.3

(cf.

Rernark

O

and

4).

From

(4.3)

we

have

(`'3)*

(,A,==2*",1;'-8((pP)'

where

R(A,

g2)40

(cf.

Lemma

8)

and whereA and

_&

are primitive

from

Lemma

3

and

(1.5).

This

systern

is

solved as

follows.

(i)

When

h*(X)EO

_(P),

we must solve only one expression

h*<X)i=O

(mod.

P).

This solution isobtained

by

_using

Theorem

3 in

g3.

(ii)

When

A(X)20

(mod.

P)

(

g,(X)EO

(mod.

P)

NII-Electronic

(8)

Nec=ecX\reet

M

19 ig

ag

1e

where

R(A,

_g2)_7EO.

This

is

solved

by

using

S4.1,

Case

1.

2. Using

a pse"do-Euclidean

(er

pgeudo-division) algorithm, when R(L, gi)=e

In

order to _perform steps of the

Euclidran

algorithm

in

Z[X],

we consider as

follows.

In

(1.1)

with

(1.2),

(1.3),

(1.4)

and

(1.5),

dividing

([rnaxA,maxgi]fmax.A)fl

by

_gi we

obtain

(cf.

Rernark

O)

(4.4)

([maxA,

max gi]lmaxA>fl=giqi+hi

where _q,

is

a monomial with respect to

X

such that

degA=deg

gi+deg

q,.

Obviously

degA>deghi

if

hivEO.

From

Lemma6 h,EO

(P).

When

hi=O,

(A,gO==gi

holds,

When

h,#O,

from R(A,gi)==O and Lemrna 8, let

h*

be the _greatest common

divisor

ofA and

gi.

Frorn

(4.-,

h"lhi

holds since h"1.fland h'lgi. And, by using

Lemma

3,

h"lhi

holds,

Hence,

from

now on, we can treat

hi

instead

of

hi.

Next, letus cornpare the

degree

of _g, with

h,.

If

one of two _polynomials

_<i.e.

_gt or

h,)

is

_greater

than or equal to the other

(gt

or hi),the

former

isdenoted by

_n

and the

latter

by

g2.

(As

we shall see

later,

in

_general,

this _procedure are sirnilar to g. and

h.

where r==1, 2,･･･.) ･

For

degn)degg2,

using the similar prooedure as

in

(4.4)

we

have

(4.s)

([maxn,

max

g2]!maxAM=g2q2+h2

where

_q2

is

a rnonomial with respect to

X

such that

degn

=degg2+degq2,

Of

course,

degA>deghe

and

h2!O

(P)･

Similarly,

h"ih2

since

h"IA

and

h"lg2

And

if

h,tO,

..., and so on.

Thus,

repeating these steps,

in

general,

for

degLldegg.

we

have

(4.6)

([rnaxL,

max _{g.]!maxi)L=g.q.+h.}

where q.

is

a monomial with respect to

X

such that

degL=degg.+degq..

And,

(4.7)

degL>degh,

if

h.#O,

(4･8)

hr!O

(P),

(4.9)

h"lh.

since

h"IL

and

h*lg.,

where r=1,

2,

･･･.

Also,

from

Lemma

9 (4.10)

(.L,

g.)2(.L+i,g.+D:

(=

(gr,

hT))

where r=1,

2,

･･･.

In

(4.7),

if

h.==O,

then g-.IL

holds

from

(4.6)

and

Lemrna

3. Also,

from

(4.9)

(9)

On the Solution

of

a Certain[ll}Pe

(4.11)

deg

_g-.

).

deg

h"

Also

from

(4.6)

and _g".rL,

gh.[L., and g-.lg.-i･

Similarly

g.IL-,

and

a,lg.-2･

Finally

g-.IA and

a.lg,･

Hence,

from

(4.11)

and

{4.9)

(4.12)

a.=h",

for

h*

is

the _primitive _polynomial and the _greatest common

divisor

of

A

and _gi.

REMARK

3. The

above-mentioned way isageneraltheory. But,

in

fact

we

had

better

use the

following

step

instead

of the above-mentioned way.

This

step

is

equivalent to

the step

in

the

former.

That

is,

(4.13)

([rnaxfl,

rnax _{gi]fmaxfl)fl-([maxfl,} max _g,]!rnax_{g,)g,Xdegfirdeg}ai!=h,

where

degA>deghi･

When h,=O,

(A,

gi>=g, holds

from

(1.5).

When

hi=O,

the

_procedure

for

finding

h*

is

similar to

(4.4)

and

(4.5)

where

h*

is

the

greatest common divisor of

A

and _gi. Henceforth, by the similar step as in above form

(4.13),

in

_general

we obtain that

(cf.

_(4.4),

(4.5)

and

(4.6))

([maxL,

max _{g.]/maxLza-([maxL,} max _g.]lmax _g.)g.Xdegfr-deggT=h.

where

clegi).degg.･

Hence

degL>degh.･

REMARK

4. As

mentionod

in

Remark

O,

in

Z[X]

we are

discussing

ways

for

finding

the solutions

in

(1.1),

for

the

integral

coeMcients can

be

interpreted

as coethcients

in

the

field

of characteristic

P

by

denoting

modulo

P. But,

if

the coeMcients

in

(1.1)

are rational, the ways

in

S4.2

are simplified since the

ideal

(fl,gi)

is

principal and

Z[X]cQ[X].

They,

however,

have

been

avoided,

for

they

refer to the

interpretation

of the coethcients

for

modulo P.

And

also, they appear lesselegant since we actually treat only an

integral

coeMcients

and modulo

P. In

(1.1)

with rational coeMcients,

however,

using the well-known

Euclidean

algorithm

we

have

AA+Bgi=C

where

fl,gieZ[X],

A,

B,

CeQ[X]

and where

C

is

the _greatest common

divisor

of

fl

and

gi

in

Q[X].

(10)

Nec=*

Jk#raN

ee

19

#

m

1

e

On

this

formula

by

multiplying

by

divisor

of the

denominators

of the coeMcients

in

the _polynomials

A,

B and

C,

we obtain

AY+B*gi=C'

where

A*,

B*,

C"

eZ[X].

Hence

(A,gi)gC*

where

(A,

gi)

is

the

ideal

in

Z[X].

Frorn

Lemma

2,3

and

8

we

have

C=h

where h* isthe _greatest common

divisor

of

A

and _gi.

3. Using

an algorithm

by

eliminating two constants

(er

briefiy A.

E. C),

when

R(4,

gt)==O

On

(1.1)

with

(1.2),

(1.3),

(1.4)

and

(1.5),

we

introduce

_a _procedure of a new type

which

finds

divisor

h*

of

A

and

_gi.

Now,

two coerncients of

Xe

in

fl

and g, are elirninated as

follows.

Frorn

degflldeg

gi we

have

(4.14)

([minA,

min

gi]/minAM-([minA, min

gi]lmin

gi)gi=X`ihi

where

degA>deghi,

minhiiO and

lill.

When

hi=O,

(A,

gi)=gi holds since

A

and _g, are _primitive.

But,

if

hitO,

then gi and

h,

are

denoted

by

fL

and g2 as mentioned

after

(4.4).

Of

course,

h"lhi

holds

since

h'IA,h*lg,

and rninh* _7EO

(cf.

(1.4)).

Thus,

repeating the same procedures as

in

(4.14),

in

general,

for

degi)degg.

we

have

(4.15)

([minL,

min g.]fminLM-([min

f;,

min

_g.]fmin

_g.)g.=Xi.h.

where minh.40,

l.ll･

Obviously

(4.16}

degL>degh.

if

h,IO,

(4.17)

h"lh.

since

h"IL

and

h'lg.,

where r=1, 2,-･..

Finally,

from

(4.16)

we

have

h.=:O

for

sorne _r(cN).

If

h,=O, then

g.1.L

holds

frorn

(4.15)

and

Lemma

10. Next,

from

the

formula

(4.15)

d.IL-i

holds･

Similarly,

g-.IL-2･

Finally

gN.]A and

g.[gi･

From

(4,17)

deg

g-.ldeg

h*

.

(11)

On the Solution

of

a Certain 71)'Pe

As

in

(4.11)

and

(4.12)

we obtain

h*

= g-r

REMARK

5. In

this section we

have

avoided to show the

formula

(4.8).

When

_fl!O

_(P)

and

g,iO

(P),

from

(4.14)

we

have

(4.18)

Xiih,!O

(P).

From

Rule

1 in

Remark

1,

if

(minfl,

min gi)=1, then

X"O

(P).

Hence,

by

(4.18)

and

Lemma

4

'

h,!O

(P).

Similariy,

from

(4.15),

L!O

(P)

and

_g.iO

(P)

hriO

(P)

where r=1,

2,･･･.

If

(minA,mingD=d;1,

however,

for

XiO

(P)

we can

finda

value of

P

from

d=

nP2ic!O

(P).

Evidently,

XiO

_(P,)

is

a selution

in

(1.1).

Next,

_putting

XIO

(P)

where

PfR,,

we can

fincl

by

performing the similar procedure

in

the preceding

case.

4.

Using

Cramer's

rule, when R(fi,gi)tO

From

(1.1)

we

form

that

r

XM'Vl=a.X"'ltMri+....+aoXmui

!E!O :

I

XM-f=

a.X"'m-2+....+a,Xm-2 =-O i

A=

a.Xbe+...+ao!O

(mod.

P)

(4.19)

/

Xn-ig,=b.X"'"-i+....+b,Xh-i

iO

1 Xa-2gi=

b.XbL'm-L'+....+boXn-2

EiEO ---l---+

gi=

b.Xm+....+b,iO

.

The

determinant

of the coeMcients in this system

is

exactly

(4.1).

Now,

consider the

Laplace

expansion

by

the components of the

(n+m)th

column

in

the

determinant

_(4.1).

In

the minors of these cofactors, at

least

one of those

is

not zero since

R(L,gi)IO.

That

is,

(4.20)

Am,n+nti#O Or An+m,ntm#O

where

Aij

denotes a cofactor in

(4.1).

(This

is

similar to the expansion

by

the components

of the

1-st

column, too).

(12)

igec=*Jit#rept rg19

g

eg

1 e

Hence,

from

(4.19)

we can choose the

(n+m-1)

expressions such that the value _of

the coeMcient

determinant

(except

for coeMcients of XO) of order

(n+m-1)

is

non-zero.

Moreover

the terms

in

this chosen system are arranged

in

ascending order of _powers

with respect to

X;

and constant terms are transposed to the right side.

Thus

we

have

the

following

system

by

Cramer's

rule:

(4･21)

doX`idi

_(P)

where

i--1,

2,--･,n+m-1

and where

do

denotes

a value of the coethcient

determinant

in

the system,

di

denotes

a value _of the

determinant

obtained by replacing the i-thcolumn

of the coeMcient

determinant

to the column of constant terms of the right side.

Hence

do,

d,eZ.

From

(4.21)

(4.22)

d,Xidj.,

_(P)

where _1"=O,

L

2,･･･,

n+m-2.

Obviously

(A,

gi)gdoX`-di.

(cf.

(5.2))

Hence,

by

Lemma 11 and 12, we can find a value of " in the form X="

_<P)

from the

system

(4.22)

as

follows.

In

the system

(4.22)

we shall try to choose

d.

and

d.

such that

(d.,

d,)=1.

If

_(d.,

d,)=

1,

then

X=-Cid..i+CEd,.,(P)

follows

where

Ci,

C2(EZ)

such that

C,d.+C2d,=1.

But,

if

(d.,

d,)#1,

from

_(4.22)

we shall try to choose

d.,

d,

and

d,

such that

_(d.,

d,,

d,)=1.

Then,

if

(d.d,,d,)=1,

we obtain

XiEC,d,.,+C2d,,,+C3dt.t

(P)

where

Ci,Ct,C3(EZ)

such that

Cid.+C2d,+Csdt=1･

But,

if

(d.

d,,d,)tl,

･･･, and so on. By

performing

these steps

re-peatedly, we may finallyarrive at

(do,

di,'`'''',

dn+m-2)

=1･

Then

we

have

n+m-2

(4.23)

X=-

_Z]

C,d,.,

_(P)

u ve+m-2

where

C,(GZ)

such that

2]

Ctdt=1.

Henceforth, by using

Theorem

1 in

S3

we can

find

o

the

desired

solution

in

(1.1)

from

(4.23)

and

Lemma

12. But,

if

(do,di,''',d.+.-r)=d;1,

then

ddi*Xiddi'+i(P)

(l=O,1,･･･,n+m-3)

follows

frorn

(4.22)

where

(4.24)

d,=dd,*

(l=O,1,･･･,n+m-2)

and where

(dD*,

di

･･･,

dn"+pt-2)==1.

Hence

we _get

n+m-2 n+m-3

(4.25)

dX='

Z

Ctdt+iiEd

Z

Cidtee-+Cn+m-2dn+m-i

(P)

e l=o

where

C,(eZ)

such that"'Si-2C,d,=d.

From

(4.24)

and

(4.25),

if

dlC.+."2d.f.-i

e

(13)

On the Sohttion

_of

Simultaneous Congruences ofa Certain 71yPe

n+pt-3

(4.26)

d(X-

Z

C,dr+,-le)-O

(P)

"

where c.+.-2d.+mri:=dk(leEz).

Then

we have two cases as follows.

Case

I:

When

diiO

(P),

letd:=fiPLk. From nPSk!!O

(P)

we can

find

a value of

P. The

solutions in

(1.1)

are obtained from

Theorem

2 in

S3.

Case

2:

When

d$O(P),

from

(4.26)

we have the following formula

ve+m-3

X-

Z

C,dr.,+k(P).

o

Hence,

using

Theorem

1 in

S3

we can find the solutions in

(1.1).

But,

if

dtc.+.T2d.+..!,

we can not

find

the

forrn

X=-a

_(P).

The

treatment of thisease

is

irnplied

in Remark

7

as

follows.

REMARK

7.

From

the

formla

R(A,

gi)=nPi"EO

(P)

(R(fl,

g,)4

O),

we can

find

the values

(i.e.

Il,)of P.

In

thisease, the _procedures

for

finding

the solution

in

(1.1)

may

frequently

be

shortened considerably.

The

treatment

by

this

formula

shows

in

S5.1.

But,

we have not used this formula, for the considerations as mentioned

in

S4.4

may

also

be

applied to

find

a solution

in

simultaneous congruences with two unknowns

X

P.

5.

Using

a representation by matrieeg, when R(L, _gi)IO

In the similar manner to that of the preceding section,

from

(4.19)

we can choose

(n+m-1)

expressions such

that

the value _of _the _coeMcient

determinant

is

non-zero.

Here, letCgd=fibe the representation by matrices of the chosen system, where

C

is the

coethcient matrix

in

this system and where _g-=(Xi),

6=(d,)

(i.e.

d,'s

are the constant

terms), i--1,2,･･･,_n+m-1.

Of

course,

C

is

regular and order

(n+m-1).

Hence

frem

Cg'=fi

and

ICIC-i==adl`

C,

it

follows

that

(4.27)

ICIe=(adj'

C)b.

Clearly,

the

formula

(4.27)

is

equivalent to the

formula

(4.21).

Hence

we can

find

the

solutions oi

(1.1)

just

as the latter

half

of

S4.4.

5. Summaries

1. Ways

for

finding

the solutions

in

(1.1)

can

briefly

be

summarized

by

the

follewing

steps.

1-ststep:

Caiculation

of the value of the

determinant

R(fl,gi)

(i.e.

(4.1))

for

the _given

system

(1.1).

2nd

step:

(A,>

WhenR(fl,gi);O:

Finding unknowns P

from

the factorization into _prime factors of the

constant number

R(Lgi),

i.e.

P=P,.

(B,)

WhenR(fl,gi)=O:

Finding

the

greatest

cornmon

divisor

h*

from

g4.2

or

S4.3.

(14)

reeczxs(\reet eg lg # ca1 e

3rd

step:

(A2)

WhenR(fl,gi)#O:

Finding

the solutions in

(1.1)

,from

Theorem2

(i)

,frorn

Rernark2

(ii)

,

from

some

formulas

in

the system

(4.22>,

i.e.

d,Xidj+i

(ll,),

]'m-O,

1,

2,

ny･･,n+m-2.

(iii)

(B2)

WhenR(fl,gi)=O:

Finding

the solutions

in

(1.1)

from

(4.3)*,

i.e.

by

Case

2,

(i)

in

g4.1

and by

Case

2,

(ii)

in

S4.1.

The

rnethod of solving

just

demonstrated

is

by

far

not the only one.

2. Ways

in

ss4:

1,2,3,4are

summarized

by

the

following

concept.

That

is,

in

the

ideal

_(A,

gi)of

(2.1)

we can _sumrnarize _these _ways.

Resultant

in

S4.1

is

a statement which shows special elements

(i.e.

the constant

num-ber,

the comrnon

factors

of

A

and _gi)in the ideal

_(A,

_gi).

That

is,

we can _eliminate

X"'m-i,

･･-,

X;

on the middle system of

(4.19)

by

multiply-ing

by

Ai..+.

(i--1,

2,

･･･, n+m), and

by

adding, where

A,f

denote

cofactors of

(4.1).

Thus

we obtain

m n

(5･1)

.fl

ZI

Ai.n+mX"-`+gi

Z

Aj+m.n+mX"-j=aoAm,n+m+boAn+m,n+m=R(]`1,gt)

t=:1

s'=1

When

R(fl,g,);O,

Rule

(Cramer)

in

S4.4

is a _statement which

find

special elements

doX`-di(i:=:1,2,.-･,n+m-1)

in

the

ideal

(fl,g,),

where

d,,diGZ.

For

example, when

An+m..+.iO

_in

_(4.20)

_we _can understand that the

form

d,X`-d,

(i=1,

2,

･･･,n+m-1) are

contained

in

the

ideal

(A,gi)

_as

follows.

If

A.+..n+.)tO,

we can treat

(n+m-1)

expressions except the expression of

(n+m)-row

in

(4.19).

That

is,

on the system

by

multiplying

by

cofactors

A,,

(le=1,2,

･･･,n+m-1)

with the

determinant

(4.1),

and

by

adding we

have

that

m n-1

(5.2)

_fl

Z

Ai,X"'`+gi

£ Ai+..,X"]'J=A.+.,.+.X"'m'"k+aoA.re

i;1 e' =1

where

le=1,

2,

･.･,n+m-1.

(i.e.

the

ideal

(fl,g,)

contains the

forrn

of the right side)

Of

course, the form doX`-di-O

_(P)

holds from Lemma 6.

When

R(fl,

gi)=O, the way in

S4.2

isan algorithm for finding a series _.L(r= 1,2,･ - ･)

such that

degL>degf;.,ll

in

the

ideal

(A,gi)

(cf.

(4.10)).

Similarly,

the

formula

L=O

(P)

holds

by

Lemma

6.

r

When

R(fl,g,)=O,

the

way

in

g4.3

is

an algorithm

for

finding

the series

X\tkh.

(r==

1,

2,･･･) such that

l,).1

and

degh.>degh..i

inthe ideal

(A,g,).

(cf.

(4.15))

And

similarly,

when

_(min.fl,

min _g,)==1 the

formula

h.iO

(P)

holds

from

Lemma

4 andRule

2 in

Remark

1 _(S

3).

From

Lemma

6,

all elements

in

the

ideal

(fl,gi)

are congruent to zero to modulus

PL

Therefore, in the course of our investigation,it is irnportant that there exist the

special elements

in

the

ideal

(A,gi),

for

example, the constant numbers, the common

divisors,

the binomials etc. By using them, the computings

for

finding

the solutions are

simp]ified.

(15)

On tlteSolution

of

Simuttaneous

Consequently,

the

qbove-mentioned

ways

imination theory and

Algorithm.

Congruences

of

a Certain

are elassfied

into

two

71yPe

easesas

fellows:

Afterword

The fundamental

idea

in this paper was _yieldedfrom an investigationof Fermat's

struc-ture

_(cf.

_[3],

_S4)

thirty _years ago.

I

believe

that this theory contributes to the _progress in many branches of mathematics.

Referenees

[1]

B,L. van derWaerden: Moderne Algebra1,Springer,1950.

[2]

P,Bachmann: Niedere ZahlentheorieI,Chelsea, 1968,pp. 368-370(Nr.19).

[3]

A. Kono:

Uber

gewisse

Aquivalenzrelationen

des RestklassenringZn, Memoirs of Sagami

Instituteof Technology, Vol.15, _pp. 35-43.