Quote:
Originally Posted by jense 2185
Never claimed to be smart, but I hoped to be lucky. Also I don't have the hardware to factor the large numbers currently.
|
Instead of just hoping to "be lucky," it would be a good idea to at least try to check your formulas for divisibility by small primes. Your formula is
N = 2*(10^X - 1)/9 + 7*10^X + 5
This formula can be expressed more compactly as follows:
N = (65*10^X + 43)/9
1) Given a prime p, p = 2, 3, 5, 7, etc are there any values of X for which p divides N?
2) If so, characterize such X (this will be a congruence class)
3) Are there any such X of a particular form, say X = 3^(2*Y + 1) + 1?
It is easy to see "by formula" that p = 2, 5, 13, and 43 can never divide N. I supply the following table for when p divides N:
p = 2: impossible "by formula"
p = 3: X == 0 (mod 3)
p = 5: impossible "by formula"
p = 7: X == 1 (mod 6)
p = 11: X == 1 (mod 2)
p = 13: impossible "by formula"
p = 17: X == 11 (mod 16)
Up to p = 17, there are no Y for which 3^(2*Y + 1) + 1 can satisfy the congruence condition for X.
I am giving you the following
homework assignment:
A) If you don't know how to do (2), learn how.
B) If you don't know how to do (3), learn how.
C) Find the smallest prime p which
can divide N = (65*10^X + 43)/9 if X = 3^(2*Y + 1) + 1, and the congruence condition on Y for which this p divides N.
The kind of checking indicated above only involves modulo arithmetic to very small moduli.