Sunan Ibn Majah Book 1, Hadith 289

حَدَّثَنَا هِشَامُ بْنُ عَمَّارٍ، حَدَّثَنَا مُحَمَّدُ بْنُ شُعَيْبٍ، حَدَّثَنَا عُثْمَانُ بْنُ أَبِي الْعَاتِكَةِ، عَنْ عَلِيِّ بْنِ يَزِيدَ، عَنِ الْقَاسِمِ، عَنْ أَبِي أُمَامَةَ، أَنَّ رَسُولَ اللَّهِ ـ صلى الله عليه وسلم ـ قَالَ ‏ "‏ تَسَوَّكُوا فَإِنَّ السِّوَاكَ مَطْهَرَةٌ لِلْفَمِ مَرْضَاةٌ لِلرَّبِّ وَمَا جَاءَنِي جِبْرِيلُ إِلاَّ أَوْصَانِي بِالسِّوَاكِ حَتَّى لَقَدْ خَشِيتُ أَنْ يُفْرَضَ عَلَىَّ وَعَلَى أُمَّتِي وَلَوْلاَ أَنِّي أَخَافُ أَنْ أَشُقَّ عَلَى أُمَّتِي لَفَرَضْتُهُ لَهُمْ وَإِنِّي لأَسْتَاكُ حَتَّى لَقَدْ خَشِيتُ أَنْ أُحْفِيَ مَقَادِمَ فَمِي ‏"‏ ‏.‏

It was narrated from Abu Umamah that:The Messenger of Allah said: "Use the tooth stick, for the tooth stick purifies the mouth and is pleasing to the Lord. Jibril never came to me but he advised me to use the tooth stick, until I feared that it would be made obligatory for me and my Ummah. Were it not that I fear that it would be too difficult for my Ummah, I would have enjoined it upon them. And I use the tooth stick until I fear that I may make the front of my mouth sore.' (i.e. my gums) (or cause my teeth to fall out due to brushing them so often)