As part of the discussion of the role of judges, the parasha discusses the trial of one who worships עבודה זרה:
<blockquote lang=he><p><b>ב</b> כי ימצא בקרבך באחד שעריך אשר ה׳ אלקיך נתן לך; איש או אשה אשר יעשה את הרע בעיני ה׳ אלקיך לעבר בריתו׃
<b>ג</b> וילך ויעבד אלהים אחרים וישתחו להם; ולשמש או לירח או לכל צבא השמים אשר לא צויתי׃</p>
<footer class=source>דברים פרק יז</footer></blockquote>
The expression אֲשֶׁר לֹא צִוִּיתִי is odd; צוה should have a direct object , the one commanded, and an indirect object, the commandment itself. This pasuk sounds like it's the צבא השמים that were not commanded. So Rashi (based on the gemara) says there's an ellipsis here; the object is the previous איש או אשה and the indirect object is the ויעבד:
<blockquote lang=he><p> <em>אשר לא צויתי</em>: לעבדם.</p>
<footer class=source>רש״י, דברים יז:ג</footer></blockquote>
That's important, since the other implication is flat-out heretical:
<blockquote lang=he><p>ופירש רש״י: ”אשר לא צויתי--לעבדם“, שאם לא כתבו לעבדם, משמע אשר לא צויתי שיהיו, ויאמרו: אם כן אלהות הן, שעל כרחו נבראו.</p>
<footer class=source>מזרחי (רא״ם), דברים יז:ג</footer></blockquote>
<blockquote lang=en><p>[A]pparently by Julius Wellhausen, "monolatry" was coined to not to express the belief in the sole existence of one god, but restriction of worship to one object of trust and loyalty, although other races might admittedly have other supernatural helpers.</p>
<footer class=source> Mackintosh, Robert (1916). <a href="https://ia801408.us.archive.org/11/items/EncyclopaediaOfReligionAndEthics.Hastings-selbie-gray.13Vols/08.EncycReligEthics.v8.Lif-D-Mul..Hastings.Selbie.Gray.1916..pdf#page=834"><cite>Monolatry and Henotheism</cite></a>. Encyclopedia of Religion and Ethics. VIII: 810.</footer></blockquote>
Wellhausen was the inventor of the JEPD model for the authorship of the Bible, and the idea that the early Israelites went from paganism to monolatry to primitive monotheism was an important part of that model:
<blockquote lang=en><p>In Wellhausen's day the theory of evolution was dominant. Darwin had won the day, and any discipline, including literature, that accepted the theory of evolution was welcomed with open arms. Furthermore, the philosopher Hegel (1770-1831) had left a deep impression in German and European culture by contending that all of history is a development from lower to progressively higher stages. It was therefore assumed that the Jewish religion developed from idolatry, and having passed through many intermediate stages, the earlier one of which was the Torah, reached the ultimate pure monotheism of latter days.</p>
<footer class=source>Rabbi Nathan Lopes Cardozo, <a href="http://www.aishdas.org/toratemet/en_cardozo.html"><cite>On Bible Criticism and Its Counterarguments</cite></a></footer></blockquote>
And the evolution of religious thought culminated in the perfection of 19th century German Protestantism.
But of course we don't read our pasuk that way. But Rashi's reading is not exactly the way the gemara reads it. The gemara says that the reading of אשר לא צויתי לעבדם was a simplification made for foreign consuption:
<blockquote lang=he><p>דתניא מעשה בתלמי המלך שכינס שבעים ושנים זקנים והכניסן בשבעים ושנים בתים ולא גילה להם על מה כינסן ונכנס אצל כל אחד ואחד ואמר להם כתבו לי תורת משה רבכם נתן הקב״ה בלב כל אחד ואחד עצה והסכימו כולן לדעת אחת וכתבו לו (בראשית א) ”אלקים ברא בראשית“ (בראשית א) ”אעשה אדם בצלם ובדמות“ (בראשית ב) ”ויכל ביום הששי וישבות ביום השביעי“...(דברים יז) ”וילך ויעבוד אלהים אחרים אשר לא צויתי לעובדם“.</p>
<footer class=source>מגילה ט,א-ב</footer></blockquote>
<hr/>
We're going to look at the pasuk differently, with כל צבא השמים as the object of לא צויתי. But the heavenly host certainly was <em>commanded</em>, as we say in פסוקי דזמרה:
<blockquote lang=he><p><b>ג</b> הללוהו שמש וירח; הללוהו כל כוכבי אור׃<br/>
<b>ד</b> הללוהו שמי השמים; והמים אשר מעל השמים׃<br/>
<b>ה</b> יהללו את שם ה׳; כי הוא צוה ונבראו׃<br/>
<b>ו</b> ויעמידם לעד לעולם; חק נתן ולא יעבור׃</p>
<footer class=source>תהילים פרק קמח</footer></blockquote>
Sforno points out that צוה without an indirect object (with no explicit command) doesn't mean <em>commanded</em> but <em>invested with authority</em>:
<blockquote lang=he><p> <em>אשר לא צויתי</em>: אשר לא מניתי בשום מנוי בחיריי שיוכלו לעשות כרצונם, אבל נתתי להם חק ולא יעבור. על היפך מחשבת עובדי עבודת גלולים שחשבו שלכל עיר ועיר יש שר יכול כרצונו להיטיב ולהרע ושהוא מטיב כשיעבדוהו .</p>
<footer class=source>ספורנו, דברים יז:ג</footer></blockquote>
And he cites similar uses of צוה:
<blockquote lang=he><p>וידבר ה׳ אל משה ואל אהרן ויצום אל בני ישראל ואל פרעה מלך מצרים; להוציא את בני ישראל מארץ מצרים׃ </p>
<footer class=source>שמות ו:יג</footer></blockquote>
<blockquote lang=he><p><em>ויצום</em>: מנה אותם לשרים, כמו ”ויסמוך את ידיו עליו ויצוהו“ (במדבר כז:כג) ”וצוך לנגיד“ (ש״א כה:ל) וזולתם </p>
<footer class=source>ספורנו, שמות ו:יג </footer></blockquote>
<blockquote lang=he><p><b>כב</b> ויעש משה כאשר צוה ה׳ אתו; ויקח את יהושע ויעמדהו לפני אלעזר הכהן ולפני כל העדה׃
<b>כג</b> ויסמך את ידיו עליו ויצוהו כאשר דבר ה׳ ביד משה׃</p>
<footer class=source>במדבר פרק כז</footer></blockquote>
<blockquote lang=he><p><b>כג</b> ותרא אביגיל את דוד ותמהר ותרד מעל החמור; ותפל לאפי דוד על פניה ותשתחו ארץ׃
<b>כד</b> ותפל על רגליו ותאמר בי אני אדני העון; ותדבר נא אמתך באזניך ושמע את דברי אמתך׃
<b>כה</b> אל נא ישים אדני את לבו אל איש הבליעל הזה על נבל כי כשמו כן הוא נבל שמו ונבלה עמו; ואני אמתך לא ראיתי את נערי אדני אשר שלחת׃
...<b>ל</b> והיה כי יעשה ה׳ לאדני ככל אשר דבר את הטובה עליך וצוך לנגיד על ישראל׃
<b>לא</b> ולא תהיה זאת לך לפוקה ולמכשול לב לאדני ולשפך דם חנם ולהושיע אדני לו; והיטב ה׳ לאדני וזכרת את אמתך׃</p>
<footer class=source>שמואל א פרק כה</footer></blockquote>
So כל צבא השמים אשר לא צויתי doesn't mean "I didn't command you to serve them" but "I didn't give them independent authority, that they should be served". And that is the basis for the Rambam's model of how עבודה זרה started in the first place:
<blockquote lang=he><p><b>כה</b> וידע אדם עוד את אשתו ותלד בן ותקרא את שמו שת; כי שת לי אלקים זרע אחר תחת הבל כי הרגו קין׃
<b>כו</b> ולשת גם הוא ילד בן ויקרא את שמו אנוש; <em>אז הוחל לקרא בשם ה׳</em>׃</p>
<footer class=source>בראשית פרק ד</footer></blockquote>
<blockquote lang=he><p><b>א</b> בימי אנוש טעו בני האדם טעות גדולה ונבערה עצת חכמי אותו הדור; ואנוש עצמו מן הטועים. וזו הייתה טעותם: אמרו הואיל והא־ל ברא כוכבים אלו וגלגלים אלו להנהיג את העולם ונתנם במרום וחלק להם כבוד והם שמשים המשמשים לפניו ראויים הם לשבחם ולפארם ולחלוק להם כבוד. וזה הוא רצון הא־ל ברוך הוא לגדל ולכבד מי שגידלו וכיבדו כמו שהמלך רוצה לכבד עבדיו והעומדים לפניו וזה הוא כיבודו של מלך.</p>
...<p><b>ג</b> וכך הם אומרים עובדיה היודעים עיקרה לא שהם אומרים שאין שם אלוה אלא כוכב זה; הוא שירמיהו אומר (ירמיהו י:ז-ח) ”מי לא ייראך מלך הגויים כי לך יאתה...“ כלומר הכול יודעין שאתה הוא הא־ל לבדך; אבל טעותם וכסילותם שמדמין שזה ההבל רצונך הוא.</p>
...<p><b>ו</b> והתחילו כוזבים אחרים לעמוד ולומר שהכוכב עצמו או הגלגל עצמו או המלאך דיבר עימהם ואמר להם עבדוני בכך וכך והודיע להם דרך עבודתו ועשו כך ואל תעשו כך. ופשט דבר זה בכל העולם לעבוד את הצורות בעבודות משונות זו מזו ולהקריב להן ולהשתחוות.</p>
<p><b>ז</b> וכיון שארכו הימים נשתקע השם הנכבד והנורא מפי כל היקום ומדעתם ולא הכירוהו; ונמצאו כל עם הארץ והנשים והקטנים אינן יודעין אלא הצורה של עץ ואבן וההיכל של בניין שנתחנכו מקטנותן להשתחוות להן ולעובדן ולהישבע בשמן.</p>
<p><b>ח</b> והחכמים שהיו בהן כגון הכומרין וכיוצא בהן מדמין שאין שם אלוה אלא הכוכבים והגלגלים שנעשו הצורות האלו בגללן ולדמותן. אבל צור העולמים לא היה שם מכירו ולא יודעו אלא יחידים בעולם כגון חנוך ומתושלח ונוח ושם ועבר. ועל דרך זו היה העולם מתגלגל והולך עד שנולד עמודו של עולם שהוא אברהם אבינו עליו השלום.</p>
<footer class=source>משנה תורה, הלכות עבודה זרה פרק א</footer></blockquote>
<hr/>
So Moshe is telling us here that serving any of the צבא השמים is, in fact, עבודה זרה and is punishable by death. But that's for בני ישראל. There's a fascinating question whether that initial mistake, the idea of שיתוף, that G-d has "partners" in running the universe, is acceptable for non-Jews. One of the שבע מצוות בני נח is the איסור עבודה זרה. But it may be far more lenient for בני נח:
<blockquote lang=he><p><b>יט</b> ופן תשא עיניך השמימה וראית את השמש ואת הירח ואת הכוכבים כל צבא השמים ונדחת והשתחוית להם ועבדתם אשר חלק ה׳ אלקיך אתם לכל העמים תחת כל השמים׃
<b>כ</b> ואתכם לקח ה׳ ויוצא אתכם מכור הברזל ממצרים להיות לו לעם נחלה כיום הזה׃</p>
<footer class=source>דברים פרק ד</footer></blockquote>
אשר חלק ה׳ אלקיך אתם לכל העמים sounds like ה׳ created צבא השמים for the other nations. Does that imply they can worship them? As with our pasuk, the Septuagint adds words to make the text benign:
<blockquote lang=he><p>דתניא מעשה בתלמי המלך שכינס שבעים ושנים זקנים...וכתבו לו...(דברים ד) ”אשר חלק ה' אלקיך אתם להאיר לכל העמים“.</p>
<footer class=source>מגילה ט,א-ב</footer></blockquote>
But there are many ראשונים who read אשר חלק ה׳ אלקיך אתם לכל העמים literally; ה׳ allows the other nations to serve צבא השמים:
<blockquote lang=he><p>ד״א <em>אשר חלק</em>, אותם לכל העמים להיות יראתם כי אינו חושש בהם.</p>
<footer class=source>חזקוני, דברים ד:יט </footer></blockquote>
And that seems to be the implication of a famous quote from מיכה (which we only remember the first part of):
<blockquote lang=he><p><b>א</b> וְהָיָה בְּאַחֲרִית הַיָּמִים יִהְיֶה הַר בֵּית ה׳ נָכוֹן בְּרֹאשׁ הֶהָרִים וְנִשָּׂא הוּא מִגְּבָעוֹת; וְנָהֲרוּ עָלָיו עַמִּים׃
<b>ב</b> וְהָלְכוּ גּוֹיִם רַבִּים וְאָמְרוּ לְכוּ וְנַעֲלֶה אֶל הַר ה׳ וְאֶל בֵּית אֱ־לֹהֵי יַעֲקֹב וְיוֹרֵנוּ מִדְּרָכָיו וְנֵלְכָה בְּאֹרְחֹתָיו; כִּי מִצִּיּוֹן תֵּצֵא תוֹרָה וּדְבַר ה׳ מִירוּשָׁלִָם׃
<b>ג</b> וְשָׁפַט בֵּין עַמִּים רַבִּים וְהוֹכִיחַ לְגוֹיִם עֲצֻמִים עַד רָחוֹק; וְכִתְּתוּ חַרְבֹתֵיהֶם לְאִתִּים וַחֲנִיתֹתֵיהֶם לְמַזְמֵרוֹת לֹא יִשְׂאוּ גּוֹי אֶל גּוֹי חֶרֶב וְלֹא יִלְמְדוּן עוֹד מִלְחָמָה׃
<b>ד</b> וְיָשְׁבוּ אִישׁ תַּחַת גַּפְנוֹ וְתַחַת תְּאֵנָתוֹ וְאֵין מַחֲרִיד; כִּי פִי ה׳ צְבָאוֹ־ת דִּבֵּר׃
<b>ה</b> <em>כִּי כָּל הָעַמִּים יֵלְכוּ אִישׁ בְּשֵׁם אֱלֹהָיו</em>; וַאֲנַחְנוּ נֵלֵךְ בְּשֵׁם ה׳ אֱ־לֹהֵינוּ לְעוֹלָם וָעֶד׃</p>
<footer class=source>מיכה פרק ד</footer></blockquote>
The question is a complex one, but the Rama concludes that the halacha is that it is acceptable for non-Jews to believe in שיתוף:
<blockquote lang=he><p>הגהה: ויש מקילין בעשיית שותפות עם הכותים בזמן הזה, משום שאין הכותים בזמן הזה נשבעים בעבודת אלילים ואף על גב דמזכירין העבודה זרה מכל מקום כוונתם לעושה שמים וארץ, אלא שמשתפין שם שמים...דהרי אינם מוזהרין על השיתוף.</p>
<footer class=source>שולחן ערוך, אורח חיים, סימן קנו</footer></blockquote>
And even in the times of משיח, when the entire world will recognize that ה׳ is the one true G-d, it may be that other religions will still exist (the Rambam is much more חמור on this issue, but the רמ״א certainly has some authority).
<blockquote lang=he><p>לפי חלק מהפירושים על דברים ד:יט, ”אֶת הַשֶּׁמֶשׁ וְאֶת הַיָּרֵחַ... אֲשֶׁר חָלַק ה' אֱ־לֹהֶיךָ אֹתָם לְכֹל הָעַמִּים“..., מותר לגויים לעבוד את ה׳ ב”שיתוף“ אלים אחרים...כפי שהסביר הרמב״ם בהלכות עבודה זרה, עבודת האלילים הייתה בתחילתה רצון לגיטימי לחלוק כבוד למשרתי ה׳ ולמלאכים הממונים על כל עם. הקלקול התחיל כששכחו את ה׳ ועבדו רק את המלאכים. הקלקול הזה גם גרם לפירוד ולמלחמות בין העמים. בעתיד, העמים יחזרו בתשובה ויעבדו את ה׳, בורא כל העולם ואלקי כל האלהים, ובמקביל כל עם ימשיך ללכת ”בשם אלהיו“ הפרטי (המלאך הממונה עליו), אבל אנחנו--עם ישראל--נלך רק בשם אלקינו לעולם ועד.</p>
<footer class=source><a href="http://tora.us.fm/tnk1/nvia/tryasr/mi-04-05.html">אראל סגל הלוי, <cite>כי כל העמים ילכו איש בשם אלהיו?!</cite></a></footer></blockquote>
It's a powerful lesson in tolerance and what לֹא יִלְמְדוּן עוֹד מִלְחָמָה really means.