(6) The Book on Traveling
أَبْوَابُ السَّفَرِ
(75) Chapter: That Starting From The Right Is Recommended In Purification
(75) باب ما يُسْتَحَبُّ مِنَ التَّيَمُّنِ فِي الطُّهُورِ
Jami` at-Tirmidhi 608 
Aishah narrated:
"The Messenger of Allah would love to start with the right side when he purified himself, and when he combed, and when putting his sandals on."
حَدَّثَنَا هَنَّادٌ، حَدَّثَنَا أَبُو الأَحْوَصِ، عَنْ أَشْعَثَ بْنِ أَبِي الشَّعْثَاءِ، عَنْ أَبِيهِ، عَنْ مَسْرُوقٍ، عَنْ عَائِشَةَ، أَنَّ رَسُولَ اللَّهِ صلى الله عليه وسلم كَانَ يُحِبُّ التَّيَمُّنَ فِي طُهُورِهِ إِذَا تَطَهَّرَ وَفِي تَرَجُّلِهِ إِذَا تَرَجَّلَ وَفِي انْتِعَالِهِ إِذَا انْتَعَلَ ‏.‏ قَالَ أَبُو عِيسَى هَذَا حَدِيثٌ حَسَنٌ صَحِيحٌ ‏.‏ وَأَبُو الشَّعْثَاءِ اسْمُهُ سُلَيْمُ بْنُ أَسْوَدَ الْمُحَارِبِيُّ ‏.‏
Grade :  Sahih (Darussalam)
Reference : Jami` at-Tirmidhi 608
In-book reference : Book 6, Hadith 65
English translation : Vol. 2, Book 1, Hadith 608