엑셀 수학ㅡ유클리드 알고리즘(두 수의 비 구하기)

 

유클리드 알고리즘을 이용한 최대공약수 구하기

두 수의 비(비율) 구하기

응용 : 유튜브 동영상 가로/세로 비율 찾아내기

최신 Ver.

유클리드알고리즘-Ver.231013.2353.xlsm

0.09MB

지오지브라

https://www.geogebra.org/calculator/dktpp4ch (98과 56)

계산기 스위트 - GeoGebra

https://www.geogebra.org/calculator/n2qrx4zs (250과 48)

계산기 스위트 - GeoGebra

이전 Ver.

유클리드알고리즘-Ver.22.0313.0914.xlsm

0.02MB

증명

A=qB+r

A=aG, B=bG (G:gcd, a와 b는 서로소)

→ aG=qbG+r  (가정::  B와 r도 G를 최대공약수로 갖는다.)

→ r=(a-qb)G   , B=bG

→ a-qb와 b는 서로소가 아니라고 가정해보자.

    그러면 공통 약수p가 있다고 가정해보자. (귀류법 시작)

     a-qb=mp,  b=np

→ a-qnp=mp → a=(m-qn)p

                           b=np            모순 (귀류법의 증명 끝)

→ 따라서 

     a-qb와 b는 서로소이고 (귀류법을 통한 결론)

     r=(a-qb)G   , B=bG 즉, r과 B는 G를 최대공약수로 갖는다.

 

Chat GPT

파이썬 파일

두수사이의소수찾기(PY).py

0.00MB