素数整除性问题

前几天遇到这么一道题，挺有趣的，分享给大家：

题目：

截图

题目的意思是：对于3的整除性，任何一个整数，如果各个位数相加能被3整除，那么这个数就能被3整除；对于11的整除性，任何一个整数，从右数每隔两位作为一个两位数进行分割，如果各个两位数相加能被11整除，那么这个数就能被11整除；是否所有的非2,5的素数p，都存在这样偏移位数r，使得分割后的数字之和能被p整除。

例如：
112321对11的整除性，
11+23+21 = 55
能被 55能被11整除，那么112321就能被11整除

很容易推导出下面公式：

任意整数X，可以表示为：
X = a₀ + 10^r * a₁ + 10^2r * a₂ + 10^3r * a₃······
= a₀ + a₁ + a₂ + a₃·····+(10^r-1) * a₁+(10^r-1) *(10^r+1) * a₂ +(10^r-1) *(10^2r+10^r+1) * a₂······
其中a_n为r位整数。若(10^r-1) 和( a₀ + a₁ + a₂ ···)能被p整除，那X就能被p整除。

引入（纯循环小数）规律一：

假设 1/p为纯循环小数
1/p = k*(1/10ⁿ+1/10²ⁿ+1/10³ⁿ·····)
其中n为循环节长度;k是循环节,为n位整数。
=> (10ⁿ - 1) 1/p = k
=> (10ⁿ - 1) = pk

引入（非2 5 素数的倒数为纯循环小数）规律二：

假设1/p为混循环小数
1/p = k(1/10^m+n+1/10^m+2n+1/10^m+3n·····)+t/10^m
其中k为n位整数，t为m位整数，k不等于t
化简得p=10^m(10ⁿ-1)/[k+(10ⁿ-1)t]
可知k只能被(10ⁿ-1)整除，设k=a*(10ⁿ-1)，带入
p = 10^m/(a+t)
=>p为素数只能取2或5
=> 1/p为纯循环小数，满足规律一。

可以得出结论

非2 5素数的倒数，一定存在整数r 、k，r为循环节长度，满足：
1/p = k/(10^r-1)
=>p*k = 10^r-1
其中k为纯循环小数循环节，长度为r

所以题目转化为求质数p的倒数的循环节长度：

import java.io.InputStreamReader;

/**
 * @author: hyp
 * Date: 2017-12-08
 */
public class Test {
    static class Expression {
        private int numerator;
        private int denominator;
        private int quotient;
        private int remainder;

        public Expression(int numerator, int denominator) {
            this.numerator = numerator;
            this.denominator = denominator;
            calculate();
        }

        private void calculate() {
            this.quotient = numerator / denominator;
            this.remainder = numerator % denominator;
        }

        public Expression next() {
            return new Expression(this.remainder * 10, denominator);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Expression)) return false;

            Expression that = (Expression) o;

            if (quotient != that.quotient) return false;
            return remainder == that.remainder;
        }

        @Override
        public int hashCode() {
            int result = quotient;
            result = 31 * result + remainder;
            return result;
        }
    }

    public static void main(String[] args) throws java.lang.Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int value = Integer.parseInt(input);
        Expression cirlcePoint = new Expression(10, value);
        Expression point = cirlcePoint;
        int times = 1;
        while (!cirlcePoint.equals(point = point.next()) && times < value) {
            times++;
        }
        System.out.println(times);
    }
}

解决了从小就被告知的，各个位数相加和能被3整除那么这个数就能被3整除的原理，而且扩展到非2 5的所有素数，是不是很开心呢~~
证明可能有不严谨的地方，希望大家不吝赐教哦~