n/m=qm+r에서 에서 m=7인 단순한 경우에도 주어진 수 n이 m의 배수 판정법은 간단하지가 않다. 만약, m이 두 자리 수 이상이 되면 더욱 복잡해진다. 일반적인 배수 판정법으로 둔켈스 (Dunkels)법이 있지만 n이 컴퓨터로 처리하지 못하는 매우 큰 자리수인 경우 이 방법도 처리할 수 없다. 본 논문은 n과 m의 자리수와 무관하게 n(modm)=0 여부로 n이 m의 배수인지 여부를 검증하는 간단하면서도 정확한 방법을 제안한다. 제안된 방법은 $n=n_1n_2n_3{\cdots}n_k$, $m=m_1m_2{\cdots}m_l$에 대해 $r_1=n_1n_2{\cdots}n_l(mod m)$으로 설정하고, $r_i=r_{i-1}{\times}10+n_i(mod m)$, $i=2,3,{\cdots},k-1+1$로 n의 자리수를 1자리씩 감소시키는 방법을 적용하였다. 제안된 방법을 다양한 n,m 데이터에 적용한 결과 쉽고, 빠르며 정확한 몫과 나머지 값을 구할 수 있음을 보였다.
n/m=qm+r에서 에서 m=7인 단순한 경우에도 주어진 수 n이 m의 배수 판정법은 간단하지가 않다. 만약, m이 두 자리 수 이상이 되면 더욱 복잡해진다. 일반적인 배수 판정법으로 둔켈스 (Dunkels)법이 있지만 n이 컴퓨터로 처리하지 못하는 매우 큰 자리수인 경우 이 방법도 처리할 수 없다. 본 논문은 n과 m의 자리수와 무관하게 n(modm)=0 여부로 n이 m의 배수인지 여부를 검증하는 간단하면서도 정확한 방법을 제안한다. 제안된 방법은 $n=n_1n_2n_3{\cdots}n_k$, $m=m_1m_2{\cdots}m_l$에 대해 $r_1=n_1n_2{\cdots}n_l(mod m)$으로 설정하고, $r_i=r_{i-1}{\times}10+n_i(mod m)$, $i=2,3,{\cdots},k-1+1$로 n의 자리수를 1자리씩 감소시키는 방법을 적용하였다. 제안된 방법을 다양한 n,m 데이터에 적용한 결과 쉽고, 빠르며 정확한 몫과 나머지 값을 구할 수 있음을 보였다.
For n/m=qm+r, there is no simple divisibility rule for simple m=7 such that is the n multiply by m? This problem can be more complex for two or more digits of m. The Dunkels method has been known for generalized divisibility test method, but this method can not compute very large digits number that ...
For n/m=qm+r, there is no simple divisibility rule for simple m=7 such that is the n multiply by m? This problem can be more complex for two or more digits of m. The Dunkels method has been known for generalized divisibility test method, but this method can not compute very large digits number that can not processed by computer. This paper suggests simple and exact divisibility method for m completely irrelevant n and m of digits. The proposed method sets $r_1=n_1n_2{\cdots}n_l(mod m)$ for $n=n_1n_2n_3{\cdots}n_k$, $m=m_1m_2{\cdots}m_l$. Then this method computes $r_i=r_{i-1}{\times}10+n_i(mod m)$, $i=2,3,{\cdots}k-l+1$ and reduces the digits of n one-by-one. The proposed method can be get the quotient and remainder with easy, fast and correct for various n,m experimental data.
For n/m=qm+r, there is no simple divisibility rule for simple m=7 such that is the n multiply by m? This problem can be more complex for two or more digits of m. The Dunkels method has been known for generalized divisibility test method, but this method can not compute very large digits number that can not processed by computer. This paper suggests simple and exact divisibility method for m completely irrelevant n and m of digits. The proposed method sets $r_1=n_1n_2{\cdots}n_l(mod m)$ for $n=n_1n_2n_3{\cdots}n_k$, $m=m_1m_2{\cdots}m_l$. Then this method computes $r_i=r_{i-1}{\times}10+n_i(mod m)$, $i=2,3,{\cdots}k-l+1$ and reduces the digits of n one-by-one. The proposed method can be get the quotient and remainder with easy, fast and correct for various n,m experimental data.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 n과 m의 자리수와 무관하게 모든 자연수 m에 대해 n이 m의 배수인지 여부를 쉽고, 빠르며, 정확하게 판정할 수 있는 방법을 제안한다. 제안된 방법은 어떠한 n과 m에 대해서도 몫과 나머지도 함께 구할 수 있는 장점을 갖고 있다.
본 논문은 n/m = qm +r에서 n,m의 자리수와 무관 하게 어떠한 수들에 대해서도 n이 m의 배수 (r = 0)인지 여부를 일반적으로 적용할 수 있는 방법을 제안하였다.
제안 방법
본 장에서는 주어진 수 n(n ≥ 2m)가 모든 자연수 m(m = 3,6,7,9,11,12,⋯)의 배수인지 여부를 쉽게 검증하는 방법을 제안한다.
본 장에서는 표 1의 17개 데이터에 대해 제안된 방법으로 n이 m의 배수인지 여부를 검증해 본다.
기존의 방법들은 특정한 하나의 m에 대해 배수법을 제안하였으며, 일반화된 방법은 Dunkels법이 유일하게 알려져 있었지만 이 방법도 n의 자리수가 커서 컴퓨터로도 표현하기 불가능할 경우 적용이 쉽지 않은 단점이 있었다. 제안된 방법은 m의 자리수 l에 대해 n에서 최좌측 자리수부터 l +1자리수의 값에 대해서만 (mod m) 의 나눗셈만을 수행하여 n의 자리수를 하나씩 감소시키는 매우 간단하면서도 k-l +1회를 수행하는 방법이다.
제안된 방법은 주어진 수 n을 MLD부터 최우측 자리수 (MRD, most right digit)로 우측으로 가면서 k-l +1≤k회 수행하는 O(k)의 선형 복잡도 알고리즘이다.
제안된 알고리즘은 n/m = qm +r에서 r을 구하기 위해서는 n = n1n2 ⋯ nk을 최좌측 자리수 (MLD, most left digit)부터 (modm)으로 구한 수로 대체시키면서 n 의 자리수를 하나씩 감소시킬 수 있다는 원리에 착안하였다. 여기서 q는 몫, r은 나머지이다.
제안된 방법은 주어진 수 n을 MLD부터 최우측 자리수 (MRD, most right digit)로 우측으로 가면서 k-l +1≤k회 수행하는 O(k)의 선형 복잡도 알고리즘이다. 제안된 알고리즘은 주어진 수 n에서 m의 배수를 계속적으로 빼면서 n의 자리수를 감소시키는 방법으로 다음과 같이 수행된다.
성능/효과
제안된 알고리즘을 다양한 n,m에 적용한 결과 k-l +1회 수행으로 몫 q와 나머지 r까지 정확히 구할 수 있음을 보였다. 따라서, 본 제안된 방법을 적용하면 배수판정법 분야에서는 추후 특정 숫자 m에 대한 배수 판정법을 고안할 필요가 없어졌으며, 기존의 배수 판정법도 의미가 없음을 알 수 있다.
제안된 알고리즘을 다양한 n,m에 적용한 결과 k-l +1회 수행으로 몫 q와 나머지 r까지 정확히 구할 수 있음을 보였다. 따라서, 본 제안된 방법을 적용하면 배수판정법 분야에서는 추후 특정 숫자 m에 대한 배수 판정법을 고안할 필요가 없어졌으며, 기존의 배수 판정법도 의미가 없음을 알 수 있다.
3장에서는 모든 자연수 m에 대해 l(n)에 무관하게, 간단하면서도 쉽게 배수 여부를 구할 수 있는 일반적인 배수 판정법을 제안한다. 제안될 방법은 l(n)이 클수록 기존의 방법들에 비해 보다 효과적으로 배수 여부를 판단할 수 있다.
질의응답
핵심어
질문
논문에서 추출한 답변
m의 배수법은 무엇인가?
분수 n/m = qm + r에서 r = 0가 되는지 여부를 검증하는 방법을 m의 배수법이라 한다. m이 한 자리수인 경우, 7을 제외한 m = 2,3,4,5,6,8,9에 대해서는 간단한 방법이 알려져 있다.
m의 자리수가 2,3,⋯으로 자리수 제약이 없는 경우의 일반화된 m의 배수법으로는 어떤 방법이 알려져 있는가?
m의 자리수가 2,3,⋯으로 자리수 제약이 없는 경우의 일반화된 m의 배수법으로는 Dunkels[2]법이 유일하게 알려져 있다. 그러나 이 방법은 n의 일의 자리수의 배수가 9로 끝나는 배수를 구하고, 나머지 n-1의 값과 일의 자리수의 배수를 더한 값이 m의 배수인지여부를 검증하는 방법이다.
m의 배수법에서,m = 7일 경우 어떠한 방법이 제안되었는가?
m이 한 자리수인 경우, 7을 제외한 m = 2,3,4,5,6,8,9에 대해서는 간단한 방법이 알려져 있다. 그러나 m = 7에 대해서는 간단한 방법이 알려져 있지 않으며, 스펜스 (Spence)법, 라이언스 (Lyons)법, 토자 (Toja)법 등을 비롯하여 다양한 방법들이 제안되었다.[1]
참고문헌 (11)
B. S. Park, "Multiple Test for 7 - Can be Divided?," Mathematics Walk, Mathematics Standard educational institute, Nov. 2009.
A. Dunkels, "Comments on Note 82.53-a Generalized Test for Divisibility," Mathematical Gazette, Vol. 84, p. 79-81, Mar. 2000.
Wikipedia, "Divisibility Rule," Wikipedia Foundation, 2013.
M. Ahuja and J. Bruening, "A Survey of Divisibility Test with a Historical Perspective," Bulletin of the Malaysian Mathematical Society, Vol. 22, pp. 33-43, 1999.
H. Feiner, "Divisibility Test for 7," The Mathematics Teacher, Vol. 58, pp. 311-312, Apr 1965.
E. R. Matthews, "A Simple 7 Divisibility Rule," The Mathematics Teacher, Vol. 62, No. 6, pp. 461-464, Oct 1969.
E. A. Maxwell, "Division by 7 or 13," Mathematical Gazette, Vol. 49, p. 84, Feb 1965.
L. E. Marin, "Why is There No Easy Divisibility Rule for 7?," Jansal Mathematics, Mar 2010.
M. B. Choi and S. U. Lee, "The $\kappa$ Fermat's Integer Factorization Algorithm," Journal of the Institute of Internet, Broadcasting and Communication, Vol. 11, No. 4, pp. 157-164, Aug. 2011.
S. U. Lee and M. B. Choi, "The Integer Factorization Method Based on Congruence of Squares," Journal of the Institute of Internet, Broadcasting and Communication, Vol. 12, No. 5, pp. 185-189, Oct. 2012.
S. U. Lee and M. B. Choi, "Integer Factorization for Decryption," Journal of the Institute of Internet, Broadcasting and Communication, Vol. 13, No. 6, pp. 221-228, Dec. 2013.
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.