The Mitzvah of Rosh Chodesh is well into the book of Shmos. If the Torah would have started there we would never have known the story of the creation of the world. We would have never heard of our forefathers, the tribes of Israel, how we descended to Egypt. The story of the Akeidah wouldn't be part of our history. Judaism would have looked completely different. Yet Rashi, with one sweep says, the Torah could have left it all out if not for what seems to be minor, an answer for the nations of the world. I'm not even sure how affective it would actually be to bring this Rashi into the UN, yet seemingly this is the justification for the whole book of Breishis!
The Talmud (Meggilah 14) asks the following question. We know, that the amount of prophets that existed in the history of Israel were twice as many as the amount of Jews that left Egypt. This means that there were well over a million Prophets in the history of the people of Israel. Yet when we count the prophets in the Bible we find 48 prophets. What happened to the rest? Answers the Talmud "A prophecy which will be needed by future generations was included in the Torah, if it won't be needed by future generations it was not included."
I once heard an explanation of this in the name of Rav Elchanan Wasserman, that in order for something to become "Torah" it has to be Netzach. Netzach means eternal. If the message of the Prophets was not needed for future generations then obviously it was not an eternal message and therefore cannot be included in the Torah.
Rashi (Talmud ibid) explains the criteria for eternity "the prophecy is needed for Teshuva (repentance) and for Horaha (decisions of Jewish law)." If it teaches us one of these then it became Torah and therefore was written if not it did not get written. Let us understand this: 1) Teshuva - probably the other million Prophets also spoke of Teshuva and thereby had an eternal message. 2) Horaha - The Talmud says in Chulin that a Prophet had no right to introduce a new Halachah to the Jewish people. Law came from Moses and could not be added upon or subtracted from by any Jew even a Prophet. So what then was the eternal value of Prophecy for Halacha?
The Maharatz Chayos asks a similar question. If it's true that a Prophet has no ability to create new laws for the Jewish people, how is it that there are many laws that we derive only from the prophets. Something as basic as Geirus (conversion) we would know very little about if it weren't for the Book of Ruth. The law that a shochet's knife must be examined before slaughtering is derived from the Book of Joshua, and many more.
The Maharatz Chayos points out that if indeed we are not to learn new Halachos from the Prophets, much of Judaism would look different. The answer is that all the laws that the Prophet taught us were well known to the people of Israel for generations. These laws were given to Moses orally and passed down through the generations. But for some reason, at the time of a particular Prophet it was decided by G-d through the Prophet that the law should transform from Oral Law to Written Law. So the Prophet said nothing new in terms of Halacha but rather made Oral into Written.
In the Sefer Niviei Emes, Rav Wolf Zal writes that he asked his teacher the Chazon Ish to explain this difficult concept. The Chazon Ish replied that this was indeed an ancient concept for the Talmud says that Moses received the whole Torah on Mt. Sinai, but he only wrote down from the beginning until the episode of giving the Torah. He then for the rest of his life prophesized from the tent of meeting. It was there that G-d instructed Moses as to how to write down what he had already known orally. In the words of the Talmud "G-d dictated and Moses repeated then wrote." Hence says the Chazon Ish Oral Law was transformed to Written law.
The question however remains, what is the significance of having the Oral law written? The strength of the Halacha is not affected by whether it is written or not, and certainly there are many Oral Laws which are better known then Written Laws. Why did G-d through his Prophets starting with Moses transfer laws from Oral to written?
We find in the Torah that the Torah itself is called "Sefer HaBris". The Ten commandments are referred to as the "Two tablets of the Bris". Bris means covenant or in simpler terms, contract. The Bris is a two way agreement between G-d and the Jewish people. G-d tells us that if we follow the Torah we will be blessed if we don't we will be cursed, if we didn't we can repent and be forgiven. This is all part of a deal that G-d made with us when we became the chosen people.
If the Torah is a contract, the Torah must be written. This is clear from the Torah itself. "G-d said to Moses, write down what I am telling you because what I am telling you constitutes a Bris." (Shmos 34;27) Rashi quotes the Talmud that from here we learn that the Oral Law must not be written and the written Law should not become oral. (Today we write down the Talmud because of extenuating circumstances.)
According to this it becomes very clear that many of the things which Moses heard on Mt. Sinai and passed on to the people of Israel were decided by G-d to become part of the agreement. Not only directives as per behavior but actually part of our contract as Jews. The Prophets never taught new Halachos but through their prophecy knew what was to become part of the Bris and what wasn't.
Perhaps this could explain that first Rashi in the Torah. Certainly if the Torah would have begun at "Hachodesh Hazeh Lochem" we still would have known all the stories of creation and of our forefathers. It would have and could have been Oral Law.
In fact so many stories of Abraham are not written in the Torah (e.g. jumping into a fiery furnace). By the fact that it was written in the Torah however we could know that its significance is not only historical or even just in its holiness, but it is actually part of the contract between G-d and Israel. In practical terms this means that the behavior of the Avos is credited towards our deeds and that we have an obligation to live up to that which was set forth for us by our forefathers. If the nations of the world, says Rashi, tell us we are thieves insofar as we take the land of Israel undeservedly we should show them the contract we have with G-d and that it was all part of the deal. This is the essence of "a prophecy for all times".