Sachverhalt: A. Mit Zahlungsbefehl vom 7. Januar 2015 (Betreibung Nr. xxx des Betreibungsamts U._) betrieb A._ B._ für Fr. 50'000.-- nebst 5 % Zins seit 4. Januar 2015. Als Forderungsurkunde gab er eine Parteivereinbarung vom 2. Mai 2014 über die Bezahlung von Mehrkosten für einen Umbau an. B._ erhob Rechtsvorschlag. B. Am 2. April 2015 verlangte A._ beim Bezirksgericht Bremgarten die Erteilung der provisorischen Rechtsöffnung für Fr. 50'000.-- nebst 5 % Zins seit 4. Januar 2015, die Zahlungsbefehlskosten (Fr. 103.30), die Rechtsöffnungskosten und die Parteientschädigung für das Rechtsöffnungsverfahren. Mit Entscheid vom 22. Juni 2015 erteilte das Bezirksgericht provisorische Rechtsöffnung für den Betrag von Fr. 50'000.-- nebst Zins zu 5 % seit 5. Januar 2015. Das Bezirksgericht hielt fest, dass A._ die Gerichtskosten von Fr. 400.-- und die Parteikosten von Fr. 2'250.-- gemäss Art. 68 SchKG von den Zahlungen von B._ vorab erheben dürfe. C. Dagegen erhob B._ am 8. Juli 2015 Beschwerde an das Obergericht des Kantons Aargau. Mit Entscheid vom 9. November 2015 hiess das Obergericht die Beschwerde gut, hob antragsgemäss den bezirksgerichtlichen Entscheid auf und wies das Rechtsöffnungsgesuch ab. Es auferlegte A._ die Gerichtskosten von Fr. 600.-- und eine Parteientschädigung an B._ von Fr. 1'140.--. D. Am 11. Januar 2016 hat A._ (Beschwerdeführer) Beschwerde in Zivilsachen an das Bundesgericht erhoben. Er beantragt die Aufhebung des obergerichtlichen Entscheids. Der bezirksgerichtliche Entscheid sei zu bestätigen, d.h. die provisorische Rechtsöffnung für Fr. 50'000.-- nebst 5 % Zins seit 5. Januar 2015 zu erteilen und dem Beschwerdeführer zu gestatten, Fr. 400.-- und Fr. 2'250.-- vorab zu erheben. Die Kosten des obergerichtlichen Verfahrens (Fr. 600.--) seien B._ (Beschwerdegegner) aufzuerlegen, ebenso eine Parteientschädigung von Fr. 1'140.-- für das obergerichtliche Verfahren. Allenfalls sei die Sache an das Obergericht zurückzuweisen. Hinsichtlich der kantonalen Kosten- und Entschädigungsfolgen sei aufschiebende Wirkung zu gewähren. Das Bundesgericht hat das Gesuch um aufschiebende Wirkung mit Verfügung vom 13. Januar 2016 abgewiesen. In der Sache hat das Obergericht auf Vernehmlassung verzichtet. Der Beschwerdegegner beantragt, die Beschwerde abzuweisen, soweit auf sie einzutreten sei.