We all live amongst non-Jews. Sometimes we meet a non-jew and befriend him because he shares the same values that we do.
Is one allowed to befriend a non-Jew?
הֱוֵי מִתַּלְמִידָיו שֶׁל אַהֲרֹן, אוֹהֵב שָׁלוֹם וְרוֹדֵף שָׁלוֹם, אוֹהֵב אֶת הַבְּרִיּוֹת וּמְקָרְבָן לַתּוֹרָה
Be of the students of Aaron: Loving peace and pursuing peace, loving mankind and bringing them close to the Torah.
(Tractate Avoth 1:12)
@Aaron: Yes, there is a negative commandment to contradict it.
The Passuk says (Devarim 7:2) "lo sechaneim (לא תחנם)." The Gemara (Avodah Zarah 20a) gives three translations: "do not give them occupation in the land (לא תתן להם חנייה)," "do not grant them favor (לא תתן להם חן)," and "do not give them free gifts (לא תתן להם מתנת חנם)."
The translation I'd like to focus on is the second one, not to grant them favor. The Gemara in Erchin (14a), in the process of its discussion regarding the Tanna of the Mishnah, brings down the ruling of Rav Yehudah in the name of Rav, that one is not allowed to say how wonderful a non-Jew is. Rashi says that the above passuk from Devarim, according to the second translation of the Gemara in Avodah Zarah, is his source.
Based on this, it may very well be prohibited.
On the other hand, there's also an Issur against a Chillul Hashem. Turning down another's efforts to befriend you might be considered a Chillul Hashem. Perhaps one could reconcile the two sources by saying that although the first Issur says that you can't go out of your way to befriend him, the second Issur would obligate you to befriend him if and only if he approaches you first. (It's perhaps for this reason that there are leniencies regarding the Issur of Lo Sechaneim. Please note that I'm not a Rav; I'm just giving what I feel is a logical reason that may very well be entirely wrong.)
As for your passuk, the Mefarshim seem to equate that positive Mitzvah with the negative one written in Shemos 22:20 - "a geir do not insult and do not oppress, for you were geirim in Mitzraim." Although I haven't gone in-depth on your passuk, the Mishnah in Bava Metzia (58b, and Gemara there) deals with the prohibition carried by the passuk in Shemos, and it clearly holds it's referring to converts: "If a person is a child of converts, don't tell him, 'Remember the deeds of your forefathers,' as the passuk says, 'a convert do not insult and do not oppress.'"
As for your problem with the second half of the passuk, don't worry; you're not the first to have posed that issue. Rashi to that passuk in Shemos says, "If you insult him, he's able to insult you and say to you, also you came from converts; any blemishes you have, don't say about your friend. Any use of 'geir' [refers to] a person who was not born there, but rather came there from somewhere else to live there." So although you're right in interpreting the second half of the passuk as referring to a stranger, not a convert, the Gemara still interprets the first half, the actual prohibition, as referring to converts. Thus, the geir's response would be: "You're insulting me because I'm spiritually a stranger? You guys were physically strangers back in Mitzraim!"
EDIT: In Kiddushin (68a), the Gemara, attempting to find a source that Kiddushin doesn't take effect between a Jew and a non-Jew, settles on the passuk of "lo sischanein bam," do not marry them (Devarim 7:3). Rashi doesn't seem to have an issue with equating the Seven Nations, of whom the passuk is speaking, and other non-Jewish nations. Tosfos, however, take issue with this point, and thus they answer that since the passuk concludes "do not give your sons to their daughters or take their daughters for your sons," we can learn two things, since the remainder of the passuk is extraneous. (Tosfos later point out that ultimately we learn it from a different passuk; this entire discussion is in the Gemara's Hava Aminah.)
According to Rashi, our passuk, too, should be able to be applied to all non-Jews. According to Tosfos, though, how can we include the Seven Nations in the prohibition of lo sechaneim?
Funny you should ask. I didn't see this the first time through, but Tosfos actually address this question in their comments to the Gemara in Avodah Zarah. He says that by any Mitzvah that you could theoretically come up with a reason that they should only apply to the Seven Nations (beyond the fact that the Seven Nations are written in the passuk) you need a special inclusion for other nations. Thus, since we have an obligation to wipe out the Seven Nations, one might think that it's only by them that there's no Kiddushin.
As for your question about killing out all non-Jews? Tosfos address that one, too. Following his above thesis, they write that it's only by the Seven Nations that we have an obligation to kill; all other nations we come across the chiyuv isn't to kill but to enslave (Devarim 20:11).
some sources. Rabbi Chaim Vital writes in Shaarei Kedusha Part 1 gate 5:
"be joyful, even during times of suffering, love all people even gentiles, don't be jealous for anything because like the shadow of the day is our time on the land".
and regarding befriending (Berachot 17): "No one ever greeted R. Yochanan ben Zakai (he always greeted first), even a Nochri (non-Jew) in the market".
On the other hand, the Rabbis forbade drinking the wine of nonjews so as not to mingle with them excessively leading to intermarriage. one has to know how to balance this. many intermarriages started out by just being friendly.
'because they share the same values as we do'
Because it is advantageous for you to be associated with people who share the same values there is no issur of lo sechanem.
Otherwise you would ostracise yourself from society.
Many Jews were saved in the holocaust due to friendships with local gentiles.
Yes! It's even a miswah to do so!
יט וַאֲהַבְתֶּם, אֶת-הַגֵּר: כִּי-גֵרִים הֱיִיתֶם, בְּאֶרֶץ מִצְרָיִם. 19
Love ye therefore the stranger; for ye were strangers in the land of Egypt.
Note: This usage of ger cannot be convert, for we were not converts to the land of Egypt. So contextually, we must love the foreigner/ the stranger. This is agreed to by the Ramban
The correct interpretation appears to me to be that He is saying: do not wrong a stranger or oppress him, thinking as you might that none can deliver him out of your hand; for you know that you were strangers in the land of Egypt and I saw the oppression with which the Egyptian oppressed you, and I avenged your cause on them, because I behold the tears of such who are oppressed and have no comforter, and on the side of their oppressors there is power, and I deliver each one from him that is too strong for him. Likewise you shall not afflict the widow and the orphan for I will hear their cry, for all these people do not rely upon themselves but trust in Me. And in another verse he added this reason: for you know what it feels like to be a stranger, because you were strangers in the land of Egypt. That is to say, you know that every stranger feels depressed, and is always sighing and crying, and his eyes are always directed towards G-d, therefore He will have mercy upon him even as He showed mercy to you, as it is written, and the children of Israel sighed by reason of the bondage, and they cried, and their cry came up to God by reason of the bondage, meaning that He had mercy on them, not because of their merits but only on account of the bondage [and likewise He has mercy on all who are oppressed.]