In thIs paper, we dIscuss strIngs of 3’s and 7’s, hereby dubbed “dreIbens.” as a fIrst step towards determInIng whether the set of prIme dreIbens Is InfInIte, we examIne the propertIes of dreIbens when dIvIded by 7. by determInIng the dIvIsIbIlIty of a dreIben by 7, we can rule out some composIte dreIbens In the search for prIme dreIbens. we are concerned wIth the number of dreIbens of length n that leave a remaInder I when dIvIded by 7. by usIng number theory, lInear algebra, and abstract algebra, we arrIve at a formula that tells us how many dreIbens of length n are dIvIsIble by 7. we also fInd a way to determIne the number of dreIbens of length n that leave a remaInder I when dIvIded by 7. further InvestIgatIon from a combInatorIal perspectIve provIdes addItIonal InsIght Into the propertIes of dreIbens when dIvIded by 7. overall, thIs paper helps characterIze dreIbens, opens up more paths of InquIry Into the nature of dreIbens, and rules out some composIte dreIbens from a prIme dreIben search. Dreibens moDulo 7 A New Formula for Primality Testing arthur dIep-nguyen IntroductIon to dreIbens and the search for InfInItely many prIme dreIbens The existence of infinitely many prime numbers is an ele- mentary fact of number theory. However, mathematicians continue to ponder over whether there are infinitely many primes of a certain kind. For instance, it is not yet known whether or not the set of Mersenne primes is finite or infinite. Evidently, questions about primes remain at the forefront of number theory. Our current research focuses on a type of number that we dubbed dreibens. Dreibens are merely strings of 3s and 7s (e.g. 333, 777, 3377373737, etc.), yet these simple strings pro- vide a foundation for a multitude of questions. Our ulti- mate goal is to prove whether or not infinitely many prime dreibens exist. While that question is beyond the scope of this paper, this paper con tributes to that goal by ruling out some composite dreibens. In fact, this paper concerns it- self with dreibens divisible by 7; by understanding dreibens modulo 7, we can rule out some dreibens that are certainly not prime. This paper uses a variety of approaches to learn about dreibens modulo 7, including techniques from number theory, abstract algebra, linear algebra, and combinatorics. With time, we hope dreibens to one day become a very well characterized type of number. learnIng about dreIbens modulo 7 by ex- plorIng Ai 7(n) We would best approach dreibens by attempting to nd the number of dreibens divisible by some number. For this paper, we interest ourselves in the number of dreibens di- visible by 7. Let us define Ai j(n) as the number 1 of dreibens of length n that leave a remainder i when divided by j. In this paper, we will concern ourselves with Ai 7(n). How do we find Ai 7(n + 1)? We can find formulas for Ai 7(n + 1) by considering the first n digits of a dreiben of length n + 1, then seeing what the last digit must be such that the dreiben leaves a remainder i when divided by 7. Let us con- sider a dreiben Dn+1 of length n + 1, which could leave a remainder of 0, 1, 2, 3, 4, 5, or 6 when divided by 7. The rst n digits of Dn+1 form another dreiben Dn that could leave a remainder of 0, 1, 2, 3, 4, 5, or 6 when divided by 7. Hence, we have seven cases, each with seven sub-cases, which we must consider. We will write the rst three cases below. 90 ElEmEnts : : spring 2016 Notice that in Case 1, Dn+1 covers all possible dreibens of length n + 1 divisible by 7. Likewise, Case 2 covers all pos- sible dreibens of length n + 1 that are 1 (mod 7), Case 3 covers all possible dreibens of length n + 1 that are 2 (mod 7), and so forth. Similarly, each subcase (a) covers all pos- sible dreibens of length n divisible by 7, each subcase (b) covers all possible dreibens of length n that are 1 (mod 7), and so forth. Hence, each case represents Ai 7(n + 1) for some i and each sub-case represents Ai 7(n) for some i. From these cases, we get the following formulas for Ai 7(n + 1) in terms of Ai 7(n): We can rewrite this linear system in terms of matrices. Let The aforementioned linear system is the same as By induction, we find that This linear system allows us to quickly find the number of dreibens of length n that leave a remainder i when divided by 7. We need only calculate the following: Let us investigate An to see if we nd anything interesting. Evidently: Let so A = B + C. "We can find formulas for Ai 7(n + 1) by considering the first n digits of a dreiben of length n + 1, then seeing what the last digit must be such that the dreiben leaves a remainder i when divided by 7." 91 Dreibens moDulo 7 If we look at the powers of B and C, we find that Notice how for i = 0 (mod 6), both Bi and Ci are equal to the identity matrix I7. Both the powers of B and C are cyclic groups of order 6. Before examining An, let us define the following: These formulas will be useful for condensing our notation. Now we can finally begin examining An: Now we have The problem with the above equation is that we still have the powers of B in terms of n. However, we can easily solve this problem because the powers of B form a cyclic group. Since this cyclic group has order 6, we must consider six cases. 92 ElEmEnts : : spring 2016 Evidently, no matter what n is, the first row of the matrix An is always Recall that If we want to find A0 7(n + 1), i.e. the first entry of →vn+1, we need only consider the first row of An: Now we have a formula with which to find the number of dreibens of length n that are divisible by 7: What if we want to find any Ai 7(n), i = 0, 1, 2, 3, 4, 5, 6? We know that these Ai 7(n) are entries of →vn. Recall that To solve for →vn+1, we must first understand An. Recall that As it turns out, A is a diagonalizable matrix, so An is also diagonalizable: Interestingly, some entries of D are 6th roots of unity. If we let be the jth ith-root of unity, then 93 Dreibens moDulo 7 Recall that the nth roots of unity form a cyclic group of or- der n, as in Table 1 below: Based on the properties of the 6th roots of unity, we find that Now that we understand Dn, we are much closer to charac- terizing An. All we need to do is to calculate PDnP-1 for each case of Dn. Below, we will calculate the first case, i.e. where n ≡ 0 (mod 6). If n ≡ 0 (mod 6), Where n ≡ 0 (mod 6), the entries of An are all either 1/7(2n – 1) or 1/7(2n + 6). Hence, An can be much more eas- ily calculated; instead of performing lengthy matrix power operations, one can merely find 1/7(2n - 1) and 1/7(2n + 6) to determine An. Since →vn = An-1→v1, one can now easily deter- mine any Ai 7(n) where n ≡ 0 (mod 6). In other words, one can easily determine the number of dreibens of length n ≡ 0 (mod 6) that leave remainder i when divided by 7. By exten- sion, one can determine the number of dreibens of length n ≡ 0 (mod 6) divisible by 7; all of these dreibens are neces- sarily composite, so they can be ruled out during our search for infinitely many prime dreibens. We can perform similar calculations for An where n ≡ 1, 2, 3, 4, 5 (mod 6), thereby allowing us to quickly find An for any n. Hence, we can easily determine An for any n, allow- ing us to rule out many composite dreibens. combInatorIal approach to dreIbens modulo 7 Let us take a combinatorial approach to Ai 7(n). For now, let us restrict ourselves to A0 7(n); in other words, we are look- ing for when a dreiben of length n is divisible by 7. These dreibens are obviously composite, so learning to identify them will help rule out composite dreibens in a prime dreiben search. 94 ElEmEnts : : spring 2016 Here, we will use the divisibility rule for 7 to aid us. Recall the divisibility rule for 7: Notice that the powers of 10 (mod 7) forms a cyclic group of order 6. Let us use the above divisibility rule to determine, as an example, 9487310294 (mod 7): Dreibens consist of only 7’s and 3’s; hence, the divisibility of a dreiben by 7 depends on both the number and place- ment of 3’s amongst its digits. (Neither the number nor placement of 7’s in a dreiben affect its divisibility by 7, as we can tell from the divisibility rule for 7.) Let Dn j(i) be the number of dreibens of length n with i number of j’s in it, e.g. Dn 3(2) is the number of dreibens of length n where 3 occupies exactly 2 digits of each dreiben. Since the divisi- bility of a dreiben by 7 depends on the number and place- ment of 3’s amongst that dreiben’s digits, we would stand to gain from investigating Dn 3(i). As you may have realized already, Evidently, by examining Dn 3(i), we can approach the prob- lem of determining the number of dreibens of length n divisible by 7. Our approach will involve investigating Dn 3(i) with varying i to see if we can make any generalizations about Dn 3(i). First, let us examine Dn 3(0). There is only one way to put exactly zero 3’s in a dreiben; every digit of that dreiben must be 7. Obviously, if a number’s digits are all 7’s, then the number is divisible by 7. Since all of the digits of a dreiben with zero 3’s is 7, and since there is only one way to make a dreiben of length n with zero 3’s, we can easily see that Dn 3(0) = 1. Next, we can examine Dn 3(1) = 0. There are no dreibens with only one 3, since 3 times any digit place 10x is never divisible by 7, so Dn 3(1) = 0. So far, we have covered two very simple instances of Dn 3(i). When i = 0, there is only a single way to make a dreiben divisible by 7. When i = 1, it is impossible to make a dreiben divisible by 7. However, as i increases, the problem of de- scribing Dn 3(i) becomes much more complicated. The next question in our investigation of Dn 3(i) involves i = 2. In other words, how many ways are there to put exactly two 3’s in a dreiben of length n? Putting exactly two 3’s in a dreiben of length n means we must choose two digit places 10x and 10y where x ≠ y and 0 ≤ x, y ≤ n - 1. Putting our two 3’s in these two digit places, we find that the dreiben is congruent to 3(10x + 10y) (mod 7). Clearly, the dreiben is divisible by 7 if and only if 10x + 10y is divisible by 7, so we need only consider 10x + 10y (mod 7). What are the possible ways to make 10x + 10y ≡ 0 (mod 7)? The powers of 10 modulo 7 form a cyclic group of order 6; without loss of generality, the possible solutions are (a) 10x ≡ 1 (mod 7), 10y ≡ 6 (mod 7) (b) 10x ≡ 2 (mod 7), 10y ≡ 5 (mod 7) (c) 10x ≡ 3 (mod 7), 10y ≡ 4 (mod 7) Another way to write the possible solutions is (a) x ≡ 0 (mod 6), y ≡ 3 (mod 6) (b) x ≡ 2 (mod 6), y ≡ 5 (mod 6) (c) x ≡ 1 (mod 6), y ≡ 4 (mod 6) For each solution, we choose one digit place each from two sets of digit places. Here, we introduce some notation that will make the later calculations more concise: • α is the set of digit places 10x ≡ 1 (mod 7), i.e. x ≡ 0 (mod 6). • β is the set of digit places 10x ≡ 2 (mod 7), i.e. x ≡ 2 (mod 6). • γ is the set of digit places 10x ≡ 3 (mod 7), i.e. x ≡ 1 (mod 6). • δ is the set of digit places 10x ≡ 4 (mod 7), i.e. x ≡ 4 (mod 6). • ε is the set of digit places 10x ≡ 5 (mod 7), i.e. x ≡ 5 (mod 6). • ζ is the set of digit places 10x ≡ 6 (mod 7), i.e. x ≡ 3 (mod 6). 95 Dreibens moDulo 7 As an example, one possible way to put two 3’s into a dreiben is to choose one digit place from α and another digit place from ζ. The number of possible combinations of choosing two digit places, one from α and one from ζ, is (|α| 1 )(|ζ| 1 ) = |α|·|ζ|. Applying this to the other sets of digit plac- es, we find that As you may have noticed, the cardinality of the six sets above depends on n (mod 6). This can be seen in Table 2 below: Hence, • If n ≡ 0 (mod 6), then • If n ≡ 1 (mod 6), then • If n ≡ 2 (mod 6), then • If n ≡ 3 (mod 6), then • If n ≡ 4 (mod 6), then • If n ≡ 5 (mod 6), then Evidently, Dn 3(2) = [ n2/12 ]. Let us prove this. Proof. If n ≡ 0 (mod 6), i.e. n = 6m where m is an integer, then If n ≡ 1 (mod 6), i.e. n = 6m + 1 where m is an integer, then If n ≡ 2 (mod 6), i.e. n = 6m + 2 where m is an integer, then If n ≡ 3 (mod 6), i.e. n = 6m + 3 where m is an integer, then 96 ElEmEnts : : spring 2016 If n ≡ 4 (mod 6), i.e. n = 6m + 4 where m is an integer, then If n ≡ 5 (mod 6), i.e. n = 6m + 5 where m is an integer, then Therefore, in general, Dn 3(2) = [ n2/12 ]. How many ways are there to put exactly three 3’s in a dreiben of length n, i.e. what is Dn 3(3)? We must choose three digit places 10x, 10y, and 10z where x ≠ y ≠ z and 0 ≤ x, y, z ≤ n - 1. Now the question is, what are the possible ways to make 10x + 10y + 10z ≡ 0 (mod 7)? In fact, there are eight cases: without loss of generality, the possible solutions are (a) 10x ≡ 1 (mod 7), 10y ≡ 1 (mod 7), 10z ≡ 5 (mod 7) (b) 10x ≡ 1 (mod 7), 10y ≡ 2 (mod 7), 10z ≡ 4 (mod 7) (c) 10x ≡ 1 (mod 7), 10y ≡ 3 (mod 7), 10z ≡ 3 (mod 7) (d) 10x ≡ 2 (mod 7), 10y ≡ 2 (mod 7), 10z ≡ 3 (mod 7) (e) 10x ≡ 2 (mod 7), 10y ≡ 6 (mod 7), 10z ≡ 6 (mod 7) (f) 10x ≡ 3 (mod 7), 10y ≡ 5 (mod 7), 10z ≡ 5 (mod 7) (g) 10x ≡ 4 (mod 7), 10y ≡ 4 (mod 7), 10z ≡ 6 (mod 7) (h) 10x ≡ 4 (mod 7), 10y ≡ 5 (mod 7), 10z ≡ 5 (mod 7) These cases can be split into two categories. Cases (b) and (f) entail choosing one digit place from each of three sets, whereas the remaining cases entail choosing two digit places from one set and one digit place from another. To describe these two categories, let us examine cases (b) and (c). In case (b), we are choosing one digit place each from the sets α, β, and ζ. Hence, the number of possible combina- tions of three digit places chosen thusly is (|α| 1 )(|β| 1 )(|ζ| 1 ) = |α|·|β|·|ζ|. In case (c), we are choosing one digit place from α and two digit places from γ. Hence, the number of possible combi- nations of three digit places chosen thusly is (|α| 1 )(|γ| 2 ) = |α|·(|γ|)(|γ|-1)/2. Describing the other cases similarly, we find that As before, since the cardinalities of the sets α through ζ are dependent on n (mod 6), we would be best served writ- ing out each of the six possible cases to see if we notice a pattern: • If n ≡ 0 (mod 6), then • If n ≡ 1 (mod 6), then • If n ≡ 2 (mod 6), then 97 Dreibens moDulo 7 • If n ≡ 3 (mod 6), then • If n ≡ 4 (mod 6), then • If n ≡ 5 (mod 6), then Table 3 summarizes what we have learned so far about Dn 3(2) and Dn 3(3): Given that Dn 3(2) = , it seems reasonable to suspect that Dn 3(3) = . Let us see if examining some values of Dn 3(3) and will enlighten us. As evident from Table 4 above, Dn 3(3) ≠ , but they seem very similar. Determining the relationship between Dn 3(3) and may be a topic for future research, but is beyond the scope of this paper. Finding Dn 3(i) for greater values of i becomes increasingly difficult, perhaps even impractical. It is beyond the scope of this paper, but should a general form for Dn 3(i) be found, one could, from a combinatorial perspective, corroborate the results of the second section, allowing one to find a different form for the explicit equation of Ai 7(n). In other words, one would have yet another method to determine the number of dreibens of length n divisible by 7. 98 ElEmEnts : : spring 2016 conclusIon While we are still far from determining whether the set of prime dreibens is finite or infinite, our exploration of dreibens modulo 7 has cast much light on the problem. Now, we have several methods to determine how many dreibens of length n are divisible by 7, therefore allowing these dreibens to be ruled out during our search for prime dreibens. We have also opened up several opportunities for inquiry. For instance, explicit matrices for An where n ≡ 1, 2, 3, 4, 5 (mod 6) must still be determined. The relation- ship between Dn 3(3) and remains a promising mys- tery, and we have yet to find a generalized formula for Dn 3(i). Although dreibens remain a mysterious type of number, current research in dreibens show promise in both uncovering new mathematical problems and achiev- ing our ultimate goal of finding infinitely many prime dreibens, if they exist. 99 Dreibens moDulo 7