We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
-1
79
4
avatar+79 

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

 May 9, 2019
 #1
avatar
+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
avatar+102466 
+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^2k^3k^4

k^5

all have

a pattern now

k^100

from pattern

0000 0
111 1
248626
397131
464646
555555
66   6666
793171
842686
919191

 

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
avatar+101872 
+2

Nice thinking, Melody   !!!!!

 

 

cool cool cool

CPhill  May 10, 2019
 #4
avatar+102466 
+1

Thanks Chris :)

Melody  May 11, 2019

15 Online Users

avatar