View Single Post
2021-09-20, 13:27   #10
Dr Sardonicus

Feb 2017
Nowhere

3·1,931 Posts

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.