The Devil's Number

Number Theory Level 3

How many positive integers $N$ are there, such that the number 666 when divided by $N$ , leaves a remainder of 66?

24 7 66 6

4 solutions

Discussions for this problem are now closed

Brian Charlesworth
Jan 30, 2015

We require that $666 \equiv 66 \mod{N} \Longrightarrow 600 \equiv 0 \mod{N}$ ,

where by necessity $N \gt 66$ . Thus we are looking for the number of factors of $600$ that exceed $66$ . These are $75, 100, 120, 150, 200, 300$ and $600$ , giving us a total of $\boxed{7}$ positive integers.

I used a similar strategy. Can you think of a more elegant strategy by which one doesn't have to actually check all the divisors?

Snehal Shekatkar - 6 years, 4 months ago

I suppose we could look at the prime factorization $600 = 2^{3}*3*5^{2}$ and count all the divisors less than $\frac{600}{66} = 9.0909....$ , which will pair with the divisors exceeding $66$ . These are $1,2,3,4,5,6$ and $8$ for a total of $7$ . We're still counting divisors but at least the numbers are smaller.

Brian Charlesworth - 6 years, 4 months ago

Unfortunately, you have to check all the divisors.

I was thinking of setting a similar questions, where we use "the number $a^2 + a$ when divided by $N$ leaves a remainder of $a$ . This way, we are looking for the divisors of $a^2$ which are greater than $a$ , and hence it is equal to $(\phi(a^2 ) - 1) / 2$ . Maybe I should do that.

Chung Kevin - 6 years, 4 months ago

Chaitanya Lodha
Feb 2, 2015

666 divided by N leaves remainder 66

therefore 600 should be divisible by N

The factors of N are 2,2,2,5,5,3

by the combinations of the multiplications of these nos, the nos bigger than 66 are the value of N which are

75,100,120,150,200,300,600

Looks good! Thanks!

Chung Kevin - 6 years, 4 months ago

Shreyash S
Feb 8, 2015

The simplest way to solve this problem.

# Python 2.7 code
x = 0
for i in xrange(667):
    if 666 % i == 66:
        x = x + 1
print x

Moderator note:

This problem does not require the use of computational aid.

Nice code, except you want to do xrange(1 , 667): because if not, you would be taking the modulo of zero, which requires dividing by 0 which is undefined, and returns and error.

David Holcer - 6 years, 3 months ago

Brock Brown
Feb 1, 2015

Python brute force:

def goal(n):
    return 666 % n == 66
n = 1
count = 0
while n <= 1000000:
    if goal(n):
        count += 1
    n += 1
print "Answer:", count

Moderator note:

This problem does not require the use of computational aid.

The Devil's Number

4 solutions

Discussions for this problem are now closed

Moderator note:

Moderator note:

0 pending reports