ぷりんの雑記帳

この記事では、Legendre 記号と Jacobi 記号の基本的な性質を、高校数学の範囲で追える形で証明します。これらの性質を使うと、平方剰余の判定をより小さな数の計算へと帰着でき、Legendre 記号や Jacobi 記号を効率よく計算できるようになります。 Legendre 記号 平方剰余と Legendre 記号 平方剰余はちょうど半分ある Eu…