Al-Nasa’i transmitted it in al-Sunan al-Kubra (2/366/2929—Hindi edition), as did al-Hakim (1/146), through him, and al-Bayhaqi (1/36). Al-Hakim said:

“Authentic according to the criteria of the two Shaykhs. Neither of them recorded in it the wording, ‘I would have made it obligatory,’ and it has no hidden defect.”

Al-Dhahabi agreed with him.

Al-Hafiz, in al-Fath (4/159), attributed it to al-Nasa’i and made no comment on it; thus, he regarded it as strong.

Al-Nasa’i then transmitted it (2934) by way of Baqiyyah, from Ubayd Allah, from Sa‘id ibn Abi Sa‘id, with the same wording.

Al-Hakim then cited in support of it a corroborating report from the hadith of Ja‘far ibn Tamam, from his father, from al-Abbas ibn Abd al-Muttalib, attributed directly to the Prophet, peace and blessings be upon him, with the wording:

“...I would have made the tooth-stick obligatory upon them at every prayer, just as I made minor ablution obligatory upon them.”

Abu Ya‘la (12/71/6710), al-Bazzar (1/243/498), and Ahmad as well (1/214) transmitted it likewise, though Ahmad did not say, “from al-Abbas.” Al-Tabarani likewise narrated it in al-Mu‘jam al-Kabir (2/64/1301–1303).

In one version recorded by Ahmad (3/442), it is from Qutham ibn Tamam—or Tamam ibn Qutham—from his father, attributed directly to the Prophet, peace and blessings be upon him. All these routes revolve around Abu Ali al-Sayqal, who is unknown. He is omitted from al-Hakim’s chain of transmission, and al-Bayhaqi records other discrepant versions as well, concluding with the words: “Its chain of transmission is disputed.”

Nevertheless, Shaykh Ahmad Shakir, may Allah have mercy on him, declared it authentic in his annotations to al-Musnad (3/246–248)! *