+0

# How many integers a

-1
175
4
+79

How many integers a from 1 to 1000 are there such that $$a^{100}-1$$ is divisible by 1000?

May 9, 2019

#1
+1

%%time c=0 for n in range(1,1001): if((n ** 100) - 1) % 1000==0: c=c+1 print(n, end=", ") print("Total = ", c)

n=1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49, 51, 53, 57, 59, 61, 63, 67, 69, 71, 73, 77, 79, 81, 83, 87, 89, 91, 93, 97, 99, 101, 103, 107, 109, 111, 113, 117, 119, 121, 123, 127, 129, 131, 133, 137, 139, 141, 143, 147, 149, 151, 153, 157, 159, 161, 163, 167, 169, 171, 173, 177, 179, 181, 183, 187, 189, 191, 193, 197, 199, 201, 203, 207, 209, 211, 213, 217, 219, 221, 223, 227, 229, 231, 233, 237, 239, 241, 243, 247, 249, 251, 253, 257, 259, 261, 263, 267, 269, 271, 273, 277, 279, 281, 283, 287, 289, 291, 293, 297, 299, 301, 303, 307, 309, 311, 313, 317, 319, 321, 323, 327, 329, 331, 333, 337, 339, 341, 343, 347, 349, 351, 353, 357, 359, 361, 363, 367, 369, 371, 373, 377, 379, 381, 383, 387, 389, 391, 393, 397, 399, 401, 403, 407, 409, 411, 413, 417, 419, 421, 423, 427, 429, 431, 433, 437, 439, 441, 443, 447, 449, 451, 453, 457, 459, 461, 463, 467, 469, 471, 473, 477, 479, 481, 483, 487, 489, 491, 493, 497, 499, 501, 503, 507, 509, 511, 513, 517, 519, 521, 523, 527, 529, 531, 533, 537, 539, 541, 543, 547, 549, 551, 553, 557, 559, 561, 563, 567, 569, 571, 573, 577, 579, 581, 583, 587, 589, 591, 593, 597, 599, 601, 603, 607, 609, 611, 613, 617, 619, 621, 623, 627, 629, 631, 633, 637, 639, 641, 643, 647, 649, 651, 653, 657, 659, 661, 663, 667, 669, 671, 673, 677, 679, 681, 683, 687, 689, 691, 693, 697, 699, 701, 703, 707, 709, 711, 713, 717, 719, 721, 723, 727, 729, 731, 733, 737, 739, 741, 743, 747, 749, 751, 753, 757, 759, 761, 763, 767, 769, 771, 773, 777, 779, 781, 783, 787, 789, 791, 793, 797, 799, 801, 803, 807, 809, 811, 813, 817, 819, 821, 823, 827, 829, 831, 833, 837, 839, 841, 843, 847, 849, 851, 853, 857, 859, 861, 863, 867, 869, 871, 873, 877, 879, 881, 883, 887, 889, 891, 893, 897, 899, 901, 903, 907, 909, 911, 913, 917, 919, 921, 923, 927, 929, 931, 933, 937, 939, 941, 943, 947, 949, 951, 953, 957, 959, 961, 963, 967, 969, 971, 973, 977, 979, 981, 983, 987, 989, 991, 993, 997, 999, Total = 400 >>Wall time: 11 ms

May 10, 2019
edited by Guest  May 10, 2019
#2
+107085
+2

How many integers a from 1 to 1000 are there such that $$a^{100}-1$$ is divisible by 1000?

$$\frac{a^{100}-1}{1000}=N\qquad where \qquad N\in (intergers \ge0)$$

My first thought was ... what possibilities are there for the last digit.

The last digit of a^100  must be 1 for any possible 'a' to be considered.

For convenience I will call the last digit k

Only last digit displayed

 k^1 k^2 k^3 k^4 k^5 all have a pattern now k^100 from pattern 0 0 0 0 0 1 1 1 1 1 2 4 8 6 2 6 3 9 7 1 3 1 4 6 4 6 4 6 5 5 5 5 5 5 6 6 6 6 6 6 7 9 3 1 7 1 8 4 2 6 8 6 9 1 9 1 9 1

Since k^100 must end in 1, k must end in 1,3, 7 or 9

But what about the other digits ???

$$\frac{a^{100}-1}{1000}=N\qquad where \qquad N\in (intergers \ge0)\\$$

I am going to let a=(10x+k)   I know that k must be  1,3,7, or 9 but I am not sure about restrictions on x

so using the binomial expansion I have

$$(10x+k)^{100}=\displaystyle\sum_{r=0}^{100}\;(10k)^r(k)^{100-r}$$

Since I want to know if this -1 is divisable by 1000 I only care about terms that are not multiples of 1000, that is not many terms.

$$(10x+k)^{100}\\=\displaystyle\sum_{r=0}^{100}\;(10k)^r(k)^{100-r}\\ =\binom{100}{0}(10x)^0(k)^{100}\;+\;\binom{100}{1}(10x)^1(k)^{99}\;+\;\binom{100}{2}(10x)^2(k)^{98}\;+\;\dots\\ =k^{100}+100(10x)(k)^{99}\;+\;4950(100x^2)(k)^{98}\;+\;\dots\\ =k^{100}+1000x*(k)^{99}\;+\;495000x^2(k)^{98}\;+\;\dots\\ =k^{100}+\;\dots\\$$

So only k, which is the last digit matters.  so long as k^100 ends in 1 then  $$(10x+k)^{100} -1$$   will be divisable by 1000

So a can be any number at all that ends in 1,3,7,9

There are 1000 numbers between 1 and 1000

10X<1000 so

X<100

There are 100 numbers that end in 1

100 that end in 3

100 that end in 7 and

100 that end in 9

So there are 400 numbers altogether that meet the requirements.     Just as our guest already determined.

May 10, 2019
edited by Melody  May 11, 2019
#3
+106539
+2

Nice thinking, Melody   !!!!!

CPhill  May 10, 2019
#4
+107085
+1

Thanks Chris :)

Melody  May 11, 2019