Not a rigorous proof but some insight perhaps...



Looking for a number of the form:

N = 37k + 18   (k is a positive integer)



Note this implies 37 divides (N-18) evenly  



37*3 = 111 so it seems at least 3, but then to get the proper remainder of 18 (N mod 37 = 18) you must make the number something like 111000 or even larger, so the last three digits can become one of {000, 001, 010, 011, 100, 101, 110, 111}.   





Here is a perl script with output showing the first 50 numbers that satisfy the condition, and the minumum number for this limited search is FIVE "1's".   There are some duplicate numbers because the way the script works, leading "0" is allowed, hence duplicates can occur:



perl -e '$len=2;$count=0;while ($count < 50) {

    for ($j=0; $j<2**$len; $j++) {

        $n = "";

        for ($i=0; $i<$len; $i++) {

            if ($j & (1<<$i)) {

                $n .= "1";

            }

            else {

                $n .= "0";

            }

        }



        if (($n % 37) == 18) {

            $count++;

            $num_1s = ($n =~ tr/"1"//);

            print "$n   ($num_1s)\n";

        }



    }



    $len++;

}



> '



1101101   (5)

01101101   (5)

101101001   (5)

101001101   (5)

001101101   (5)

1101101000   (5)

1101001100   (5)

1001101100   (5)

1101100001   (5)

1100101001   (5)

0101101001   (5)

1101000101   (5)

1001100101   (5)

1100001101   (5)

0101001101   (5)

1000101101   (5)

0001101101   (5)

1111101101   (8)

1101111101   (8)

1101101111   (8)

01101101000   (5)

01101001100   (5)

01001101100   (5)

10110110010   (6)

10110010110   (6)

10010110110   (6)

01101100001   (5)

01100101001   (5)

00101101001   (5)

01101000101   (5)

01001100101   (5)

01100001101   (5)

00101001101   (5)

01000101101   (5)

00001101101   (5)

11101101101   (8)

01111101101   (8)

01101111101   (8)

01101101111   (8)

101101001000   (5)

101001101000   (5)

001101101000   (5)

101001001100   (5)

001101001100   (5)

001001101100   (5)

110110010010   (6)

110010110010   (6)

010110110010   (6)

110010010110   (6)

010110010110   (6)

010010110110   (6)

101101000001   (5)

101001100001   (5)

001101100001   (5)

101100001001   (5)

100101001001   (5)

101000101001   (5)

001100101001   (5)

100001101001   (5)

000101101001   (5)

111101101001   (8)

101111101001   (8)

101101111001   (8)

101001000101   (5)

001101000101   (5)

001001100101   (5)

101000001101   (5)

001100001101   (5)

100001001101   (5)

000101001101   (5)

111101001101   (8)

101111001101   (8)

001000101101   (5)

000001101101   (5)

111001101101   (8)

011101101101   (8)

101011101101   (8)

001111101101   (8)

101101011101   (8)

101001111101   (8)

001101111101   (8)

101101101011   (8)

101101001111   (8)

101001101111   (8)

001101101111   (8)



----

Good analysis by tutor greenestamps, thanks for posting!

 VVVVV      VVVVV      VVVVV       VVVVV      VVVVV





-----

Added 7/10/21:



The proof can be completed.   As tutor greenestamps points out, the decimal numbers consisting of only "1" and "0" digits which are equal to 18 mod 37, must consist of linear combinations of 26, 10, and 1 in the ABC positions he has outlined:



18:

  (1) 18 = 1(10) + 8(1)  --> 9 digits

  (2) 18 = 18(1)          ---> 18 digits   (clearly we don't need to check all 1's cases)



18+37=55:

   (1) 55 = 2(26) + 3(1)  --> 5 digits

   (2) 55 = 1(26) + 2(10) + 9(1)  -->  12 digits

   (3) 55 = 5(10) + 5(1)  -->  10 digits



55+37=92:

    (1) 92 = 3(26) + 1(10) + 4(1) --> 8 digits

    (2) 92 = 2(26) + 4(10)  -->  6 digits

    (3) 92 = 1(26) + 6(10) + 6(1) --> 13 digits



92+37=129:

    (1) 129 = 4(26) + 2(10) + 5(1) --> 11 digits

    (2) 129 = 3(26) + 5(10) + 1(1) --> 9 digits

   (any fewer 26s and you have more than 6 10s hence more than 6 digits)



 

129+37=166:

     (1) 166 > 5*26   --> MORE THAN 5 digits required





Therefore, the minimum number of digits is indeed 5.  Proof complete.







 

Answer by greenestamps(13200)   (Show Source): You can put this solution on YOUR website!
 


Thanks to tutor #math_helper for his response to your question, which has helped me finish the analysis of the problem I had started on.


The requirements of the problem are that an integer N must contain only digits 0 and 1, and that N leave remainder 18 when divided by 37  -  i.e., N-18 is a multiple of 37, or mod(N-18,37)=0.


The analysis below will allow us to find as many integers as we want that satisfy the conditions.  An assertion will be made -- but not formally proved -- that the minimum number of 1's in the number is 5.


To analyze the problem, we know that the value of an integer mod 37 is the sum of the values mod 37 of the digits in each place in the number.  If the only non-zero digits are 1’s, then the value of the integer mod 37 is the sum of the mod 37 values of the place values where the 1’s are.


So we find the pattern in the mod 37 values of the place values  -  i.e., the mod 37 values of the powers of 10.


mod(10^0,37) = 1

mod(10^1,37) = 10

mod(10^2,37) = 26

mod(10^3,37) = 1


We see that the mod 37 values of the place values in base 10 follow a pattern with a cycle of length 3.


So let’s write our number N with the digits grouped in groups of 3, just as we often do when writing large numbers in base 10.  E.g., a number might look like this: BC,ABC,ABC,ABC,ABC,ABC,ABC,ABC.


Then a 1 in any “C” place will have a mod 37 value of 1; a 1 in any “B” place will have a mod 37 value of 10; and a 1 in any “A” place will have a mod 37 value of 26.  And of course the 0’s in all the other places have a mod 37 value of 0.


We want our numbers N to be equal to 18 mod 37, so we can look for linear combinations of 1, 10, and 26 that are equal to 18 mod 37.


There is no linear combination of 1, 10, and 26 that is equal to 18.


Add 37 to 18 and we need linear combination(s) that sum to 55.


This we can do: 2(26)+3(1)=55.


That means any number with 2 1’s in the “A” places and 3 1’s in the “C” places will leave a remainder of 18 when divided by 37.


The smallest such number is N = 1,101,101; checking verifies that N-18 =1,101,083 is divisible by 37.


But there are obviously an infinite number of other numbers that have 1’s in two “A” places and in 3 “C” places:

N = 1, 001,001,100,100

N = 1,000,000,000,100,100,000,001,001

etc.


Again calculation shows that for each of those numbers N-18 is divisible by 37.


Finally, in the context of the problem, note that in any of these numbers the number of 1's is 2+3=5.


So we had no linear combinations of 1, 10 and 26 adding to 18; then we had one linear combination of 1, 10, and 26 adding to 18+37=55.  Next we look for linear combinations of 1, 10, and 26 adding to 55+37=92.


There are (at least) two:

2(26)+4(10)=92

3(26)+1(10)+4(1)=92


The first of these linear combinations means any number with 1's in 2 "A" positions and 4 "B" positions will be an N that satisfies the conditions of the problem -- e.g.

10,010,011,011


Obviously for any number like that, the number of 1's in the number is 2+4=6.


The second of these linear combinations means any number with 1's in 3 "A" positions, 1 "B" position, and 4 "C" positions will be another number that satisfies the conditions of the problem.  The smallest such number is

1,101,101,111.


Obviously in any number of this form the number of 1's will be 3+1+4=8.


So we have found ways to find an unlimited number of numbers N with 5, 6, or 8 1's that satisfy the conditions of the problem.  I did not find any with 7 1's, or any with less than 5 1's.  And there undoubtedly numbers N that satisfy the conditions of the problem that have more than 8 1's.


In the end, the answer -- although not formally proved -- is that the minimum number of 1's in the numbers that satisfy the conditions of the problem is 5.


----------------------------------------------------------------------


Note that each of the solutions found by the computer program used by the other tutor is of one of the three forms found by the above analysis.


 

RELATED QUESTIONS

All the digits of the positive integer N are either 0 or 1. The remainder after dividing... (answered by greenestamps)

What is the smallest positive integer n so that 13n leaves a remainder of 1 when divided... (answered by Theo)

a)  What is the remainder left after dividing
                              1! + 2! + 3!  (answered by venugopalramana)

What is the least positive integer meeting each of the following conditions?
Dividing by  (answered by MathLover1)

What is the sum of all positive integer values of n such (n+20)/n is an integer... (answered by jim_thompson5910)

What is the sum of all positive integer values of n such (n
+24)/n is an... (answered by Edwin McCravy)

What is the smallest positive integer {{{n}}} such that all the roots of {{{z^4 + z^2 + 1  (answered by ikleyn)

What is the least possible positive integer value of n such that 18 x n x 34 is an... (answered by stanbon!)

If n is a positive integer then what is the remainder when {3(8n+3)+2} is divided by... (answered by josgarithmetic)