高中数学竞赛讲义(17)整数问题(共8页).doc

精选优质文档-倾情为你奉上高中数学竞赛讲义（十七）整数问题一、常用定义定理1整除：设a,bZ,a0，如果存在qZ使得b=aq，那么称b可被a整除，记作a|b，且称b是a的倍数,a是b的约数。b不能被a整除，记作a b.2.带余数除法：设a,b是两个给定的整数，a0，那么，一定存在唯一一对整数q与r，满足b=aq+r,0r|a|，当r=0时a|b。3辗转相除法：设u0,u1是给定的两个整数，u10，u1 u0,由2可得下面k+1个等式：u0=q0u1+u2,0u2|u1|；u1=q1u2+u3,0u3u2；u2=q2u3+u4,0u4u3；uk-2=qk-2u1+uk-1+uk,0ukuk-1；uk-1=qk-1uk+1,0uk+11且n为整数，则，其中pj(j=1,2,