Sachverhalt:
A.
X._ sagte am 18. November 2013 als Zeuge vor der Staatsanwaltschaft Brugg-Zurzach falsch aus.
B.
Die Staatsanwaltschaft Brugg-Zurzach sprach X._ mit Strafbefehl vom 16. Januar 2014 des falschen Zeugnisses und der versuchten Begünstigung schuldig. Sie bestrafte ihn mit einer bedingten Freiheitsstrafe von sechs Monaten bei einer Probezeit von vier Jahren sowie mit einer Busse von Fr. 2'500.--.
Auf Einsprache hin sprach die Präsidentin des Bezirksgerichts Brugg X._ von Schuld und Strafe frei mit der Begründung, die Falschaussage sei nicht wissentlich und willentlich erfolgt.
Auf Berufung der Staatsanwaltschaft Brugg-Zurzach verurteilte das Obergericht des Kantons Aargau X._ wegen falschen Zeugnisses. Vom Vorwurf der versuchten Begünstigung sprach es ihn frei. Das Obergericht auferlegte X._ eine bedingte Geldstrafe von 60 Tagessätzen zu Fr. 80.-- bei einer Probezeit von drei Jahren sowie eine Busse von Fr. 500.--.
C.
X._ führt Beschwerde in Strafsachen. Er beantragt, das Urteil des Obergerichts sei mit Ausnahme des Freispruchs aufzuheben, und er sei von Schuld und Strafe freizusprechen. Für seine Aufwendungen in den vorinstanzlichen Verfahren und die erlittene Untersuchungshaft sei er mit mindestens Fr. 12'899.15 zu entschädigen. Zudem ersucht er um aufschiebende Wirkung.
D.
Die Oberstaatsanwaltschaft und das Obergericht des Kantons Aargau haben auf eine Vernehmlassung verzichtet.

Erwägungen:
1.
Der Beschwerdeführer wirft der Vorinstanz vor, den Sachverhalt willkürlich gewürdigt und den Grundsatz "in dubio pro reo" im Sinne von <ref-law> verletzt zu haben (Beschwerde S. 13 ff.).
1.1. Die vorinstanzliche Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; vgl. auch Art. 105 Abs. 1 und 2 BGG). Offensichtlich unrichtig im Sinne von <ref-law> ist die Sachverhaltsfeststellung, wenn sie willkürlich ist (<ref-ruling> E. 1.3.1 S. 253 mit Hinweis; vgl. zum Begriff der Willkür <ref-ruling> E. 2.1 S. 18 f.; <ref-ruling> E. 3.2.5 S. 339; <ref-ruling> E. 7.1 S. 51; je mit Hinweisen).
Inwiefern das Sachgericht den Grundsatz "in dubio pro reo" als Beweiswürdigungsregel verletzt hat, prüft das Bundesgericht ebenfalls unter dem Gesichtspunkt der Willkür. Diese aus der Unschuldsvermutung abgeleitete Maxime wurde wiederholt dargelegt, worauf zu verweisen ist (<ref-ruling> E. 2a S. 41 mit Hinweisen).
Die Rüge der Verletzung von Grundrechten (einschliesslich Willkür bei der Sachverhaltsfeststellung) muss in der Beschwerde anhand des angefochtenen Entscheids präzise vorgebracht und substanziiert begründet werden, anderenfalls darauf nicht eingetreten wird (<ref-law>; <ref-ruling> E. 1.3.1 S. 253; <ref-ruling> E. 2.2 S. 232; je mit Hinweisen).
1.2. Im Strafverfahren gegen A._ betreffend Tötungsdelikt zum Nachteil dessen Ehefrau B._ wurde der Beschwerdeführer am 18. November 2013 als Zeuge vor der Staatsanwaltschaft Brugg-Zurzach befragt. Schwerpunkte der Einvernahme waren einerseits die familiären Verhältnisse seines Bruders A._ sowie (in einem zweiten Teil der Befragung) die familiären Verhältnisse des Zeugen persönlich. Im Anschluss an die Zeugeneinvernahme wurde der Beschwerdeführer wegen Verdachts eines falschen Zeugnisses verhaftet und drei Tage später vom Zwangsmassnahmengericht auf freien Fuss gesetzt.
Nach den vorinstanzlichen Feststellungen habe der Beschwerdeführer wiederholt zu Protokoll gegeben, sein Bruder A._ habe zwei Kinder. Hingegen sei erstellt, dass A._ in der Türkei vier Söhne habe. Der Beschwerdeführer habe die Frage nach der Anzahl Kinder wahrheitswidrig beantwortet. Er habe gewusst, dass A._ nicht lediglich zwei Kinder habe (Entscheid S. 5 ff.). Das Bezirksgericht Brugg äusserte demgegenüber erhebliche Zweifel, dass der Beschwerdeführer von den jüngeren beiden Söhnen seines Bruders wusste (erstinstanzlicher Entscheid S. 13 ff.).
1.3. Der Beschwerdeführer stellt sich zusammengefasst auf den Standpunkt, er habe den subjektiven Tatbestand des falschen Zeugnisses nicht erfüllt. Die Vorinstanz habe seine Aussagen tendenziös gewürdigt, ihm grundlos eine Verschleierungsabsicht unterstellt und klar entlastende Momente ausgeblendet. Die Mehrheit der von der Staatsanwältin gestellten Fragen habe in keinem erkennbaren Zusammenhang mit dem gegen A._ geführten Strafverfahren gestanden. Dass man ihn eingehend zum Beziehungsstatus und der Anzahl Kinder seines Bruders befragt habe, habe ihn deshalb verständlicherweise irritiert. Er habe insgesamt zehn Geschwister, pflege zu ihnen einen nur sehr sporadischen Kontakt und lebe seit mehr als 21 Jahren in der Schweiz. Im Rahmen der gegen A._ geführten Strafuntersuchung seien mehrere seiner Geschwister und Verwandten befragt worden. Auch zwei weitere Brüder sowie ein Cousin hätten nicht gewusst, dass A._ vier Kinder habe respektive mit C._ verheiratet gewesen sei. Diesen Umstand blende die Vorinstanz ebenso aus wie die Aussagen einer weiteren Zeugin, wonach A._ nach ihrem Wissen nur zwei Söhne habe. Mit diesem entlastenden Indiz habe sich die Vorinstanz in keiner Weise auseinandergesetzt, obgleich es von der ersten Instanz zu seinen Gunsten gewürdigt worden sei. Er müsse seine Unschuld nicht beweisen. Der Schuldspruch der Vorinstanz basiere auf Vermutungen anstatt auf Fakten (Beschwerde S. 13 ff.).
1.4. Vorinstanzliches Beweisfundament sind die Aussagen des Beschwerdeführers anlässlich der staatsanwaltschaftlichen Einvernahme vom 18. November 2013 und der erstinstanzlichen Hauptverhandlung. In Bezug auf die staatsanwaltschaftliche Einvernahme würdigt die Vorinstanz die erste Antwort des Beschwerdeführers zur Frage, ob sein Bruder Kinder habe (Untersuchungsakten pag. 119), ob dieser noch mit C._ nach Brauch verheiratet sei (sogenannte "Imam-Ehe"; Untersuchungsakten pag. 120 f.) und ob sein Bruder mehr als zwei Kinder haben könnte, von denen der Beschwerdeführer nichts wisse (Untersuchungsakten pag. 123). Die Vorinstanz gelangt zur Überzeugung, der Beschwerdeführer habe bereits zu Beginn der Befragung eine ablehnende Haltung an den Tag gelegt und die Frage nach einer allfälligen Scheidung ebenfalls vage und ausweichend beantwortet. Zudem sei nicht nachvollziehbar, weshalb der Beschwerdeführer nichts von allfälligen Kindern hätte wissen können, die sein Bruder mit einer anderen Frau als C._ gezeugt habe. Insgesamt mute das Aussageverhalten des Beschwerdeführers vor der Staatsanwaltschaft seltsam an. Es lege "die Vermutung nahe, dass er bezüglich der familiären Verhältnisse seines Bruders etwas zu verheimlichen versuchte resp. darum bemüht war, seinen Bruder zu decken".
1.5.
1.5.1. Verfahrensgegenstand war ein im Jahre 2013 begangenes Tötungsdelikt in Brugg zum Nachteil von B._. Der Beschwerdeführer wurde als Zeuge vorgeladen und schwergewichtig zur Ehesituation seines Bruders mit C._ und zur Anzahl Kinder befragt. Aus dieser Ehe sind 1996, 1999, 2004 und 2009 vier Kinder hervorgegangen. Die Staatsanwaltschaft Brugg-Zurzach verfügte spätestens einen Monat vor der Einvernahme des Beschwerdeführers über die Namen und Geburtsdaten dieser vier Kinder (Entscheid S. 13; vgl. auch Untersuchungsakten pag. 110 ff.). Weitere Fragen betrafen eine frühere Ehe von A._, welche bereits im Jahre 2007 aufgelöst und im Jahre 2009 rechtskräftig als Scheinehe qualifiziert worden war. Wenige Fragen betrafen schliesslich die Beziehung des Beschuldigten zum Opfer. Die zweite Hälfte der Befragung drehte sich um die eigene aufgelöste Ehe des Zeugen, was das A._ vorgeworfene Tötungsdelikt nicht im Ansatz tangierte.
Die Vorinstanz erkennt bereits in der ersten protokollierten Antwort zur Frage der Kinder wie auch in den Aussagen betreffend die Ehe mit C._ eine ablehnende und ausweichende Haltung des Beschwerdeführers. Diese Würdigung erscheint unter Willkürgesichtspunkten gerade noch vertretbar. Gleichwohl bleibt anzufügen, dass der Beschwerdeführer in der nämlichen Einvernahme über 20 weitere Fragen betreffend die Kinder seines Bruders beantwortete, was das ihm vorgeworfene ablehnende Verhalten zumindest relativiert. Zudem war er nach seiner Darstellung und mit einer gewissen Berechtigung über den Gegenstand der Befragung irritiert. Selbst wenn die Staatsanwaltschaft die Glaubwürdigkeit des Zeugen prüfen wollte (vgl. <ref-law>), konfrontierte sie ihn mit einer Vielzahl von Fragen, die in keinem Zusammenhang zum Tötungsdelikt standen. Der Beschwerdeführer bringt im Übrigen mangelnde Sprachkenntnisse vor, die nicht ohne Weiteres von der Hand zu weisen sind (die staatsanwaltschaftliche Befragung vom 18. November 2013 erfolgte ohne Beizug eines Dolmetschers, dies im Gegensatz zu sämtlichen folgenden Einvernahmen durch die Staatsanwaltschaft, das Zwangsmassnahmengericht und die erste Instanz).
Hingegen kann der Vorinstanz nicht gefolgt werden, es sei nicht nachvollziehbar, weshalb der Beschwerdeführer nichts von allfälligen Kindern hätte wissen können, die sein Bruder mit einer anderen Frau als C._ gezeugt hätte. Der Beschwerdeführer hat mit der fraglichen Aussage offensichtlich die Möglichkeit thematisiert respektive nicht ausgeschlossen, dass sein Bruder weitere Kinder hat, von denen er (der Beschwerdeführer) keine Kenntnis hat. Es kann nicht gesagt werden, eine solche Aussage sei nicht nachvollziehbar (vgl. auch den erstinstanzlichen Entscheid S. 16).
1.5.2. Insgesamt weisen die Aussagen des Beschwerdeführers vom 18. November 2013 nicht nach, dass er von den vier in der Türkei lebenden Kindern seines Bruders mit C._ Kenntnis hatte. Diesen Schluss zieht auch die Vorinstanz nicht. Sie hegt einzig die blosse Vermutung, dass der Beschwerdeführer "bezüglich der familiären Verhältnisse seines Bruders etwas zu verheimlichen versuchte [...]". In einem nächsten Schritt würdigt die Vorinstanz die Aussagen des Beschwerdeführers vor Schranken. Dieser hielt anlässlich der erstinstanzlichen Hauptverhandlung Folgendes fest: "Als Ibrahim in die CH kam, hatte er zwei Kinder. Weil ich mit ihm wenig Kontakt hatte und mit ihm nicht viel in dieser Beziehung über das geredet hatte, wusste ich nur von zwei Kindern. Man hat nicht über das gesprochen. Ich habe dann mit einem anderen, jüngeren Bruder in der Türkei geredet, als das mit dem Bruder Ibrahim passierte. Als Ibrahim festgenommen wurde, habe ich mit dem jüngeren Bruder in die Türkei telefoniert. Dann habe ich von ihm erfahren, dass Ibrahim vier Kinder hat" (vorinstanzliche Akten pag. 19). Da B._ am 23. Juli 2013 getötet und A._ kurz danach festgenommen worden sei, habe der Beschwerdeführer laut Vorinstanz spätestens "um diesen Zeitpunkt" von allen vier Kindern seines Bruders gewusst. Deshalb bestünden keine Zweifel, dass der Beschwerdeführer bereits anlässlich der Einvernahme vom 18. November 2013 Kenntnis der fraglichen Umstände gehabt habe. Diese Schlussfolgerung ist nicht haltbar. Der Beschwerdeführer räumte zwar ein, er habe nach der Verhaftung seines Bruders mit dem jüngeren Bruder in der Türkei telefoniert. Der Zeitpunkt des fraglichen Telefongesprächs wurde jedoch von ihm nicht genannt und von der ersten Instanz nicht näher erfragt. Der Zeitpunkt des Telefongesprächs ist aus Sicht der Vorinstanz - da diese gestützt auf die staatsanwaltschaftliche Befragung ein vage umschriebenes Verheimlichen vermutet - eigentlicher Angelpunkt. Die Feststellung, dass das Telefongespräch nicht nur nach der Verhaftung, sondern vor der fraglichen Befragung stattfand, geht nicht über eine blosse Hypothese hinaus. Sie wird nicht näher begründet, lässt sich auf kein Beweisfundament stellen und ist damit unhaltbar. Es kann deshalb offenbleiben, ob der Beschwerdeführer wie von ihm vorgebracht anlässlich der erstinstanzlichen Hauptverhandlung nicht auf die Verhaftung seines Bruders, sondern auf die eigene Verhaftung im Anschluss an die fragliche Einvernahme vom 18. November 2013 Bezug nahm.
1.5.3. Am 30. Oktober 2013 wurde D._, die Schwiegertochter der getöteten B._, als Zeugin von der Staatsanwaltschaft Brugg-Zurzach zum Tötungsdelikt befragt. Aus dem Protokoll der dreistündigen Befragung geht unschwer hervor, dass die Zeugin zu ihrer Schwiegermutter ein gutes und nahes Verhältnis hatte, sehr viele Details über deren Leben und die Beziehung zu A._ kannte, im Laufe der Zeit zur eigentlichen Ansprechsperson wurde und ihr in schwierigen Zeiten beistand. Aufgrund eines Vorfalls wegen häuslicher Gewalt gab das Opfer die Telefonnummer seiner Schwiegertochter bei der Polizei an und wohnte zwei Monate bei ihr. Auf die Frage der Staatsanwältin, die Zeugin wisse fast mehr über B._ als die Kinder des Opfers, führte die Zeugin aus: "Ja, das ist so. Bei E._ weiss ich es nicht genau. Sicher bei F._. B._ hat mir immer sehr viel anvertraut. Von Problemen. Ich habe auch nachgefragt, auch in Bezug auf die Vergangenheit von ihm." Es kann deshalb ohne Weiteres gesagt werden, dass die Zeugin und ihre Schwiegermutter ein enges Verhältnis hatten und diese sich ihrer Schwiegertochter anvertraute (vgl. Untersuchungsakten pag. 157 ff.).
In der Einvernahme gab die Zeugin an, A._ habe zwei Söhne und B._ habe die Kinder ein- oder zweimal in der Türkei getroffen (Untersuchungsakten pag. 162 und 171). Diese Aussage ist bemerkenswert. Sie lässt - soweit die Zeugin nicht bewusst falsch aussagte, wofür keine Hinweise erkennbar sind - nur zwei Schlussfolgerungen zu. B._ wusste nur von zwei Kindern ihres Ehemannes und lernte diese in der Türkei kennen, obwohl ihr Ehemann zur besagten Zeit aus der "Imam-Ehe" bereits vier Kinder hatte. Damit wurde sie von A._ über die anderen zwei Kinder im Dunkeln gelassen. Oder aber B._ kannte die wahren Verhältnisse und spiegelte ihrer Schwiegertochter in diesem Punkt etwas vor. Die zweitgenannte Variante drängt sich aufgrund der Beziehung zwischen Opfer und Zeugin nicht auf. Zudem heirateten A._ und B._ laut Zeugin im Jahre 2009, während das jüngste Kind aus der "Imam-Ehe" im Januar 2009 zur Welt kam. Es musste deshalb für das Opfer einerlei gewesen sein, ob sein Ehemann aus einer früheren Ehe zwei oder vier Kinder hatte.
Der Beschwerdeführer bringt deshalb zutreffend vor, er werde durch die Aussagen der Zeugin entlastet. Indem sich die Vorinstanz damit nicht auseinandersetze, verletze sie den Grundsatz "in dubio pro reo". Die Rüge ist begründet. Die Sachdarstellung des Beschwerdeführers erfährt durch die Zeugenaussagen von D._ eine gewichtige Unterstützung. Die erste Instanz hielt dazu fest, auch die Zeugin D._ habe nur von zwei Söhnen gewusst, was für die Darstellung des Beschwerdeführers spreche (erstinstanzlicher Entscheid S. 16). Die Vorinstanz setzt sich mit dem entlastenden Beweismittel in ihrer Beweiswürdigung nicht auseinander. Die erste Instanz hat das besagte Beweismittel zu Gunsten des Beschwerdeführers gewürdigt und ihn vom Tatvorwurf freigesprochen. Deshalb ist es umso unverständlicher und im Ergebnis nicht haltbar, dass die Zeugenaussagen im vorinstanzlichen Entscheid mit keinem Wort erwähnt und in der Beweiswürdigung letztendlich unterschlagen werden.
1.5.4. Die Befragung des Beschwerdeführers vom 18. November 2013 begründet nach Einschätzung der Vorinstanz die blosse Vermutung, der Beschwerdeführer habe in Bezug auf die familiären Verhältnisse von A._ etwas zu verheimlichen versucht. Diese Mutmassung lässt sich gestützt auf das vom Beschwerdeführer erwähnte Telefongespräch mit einem jüngeren Bruder nicht zum Tatvorwurf erhärten (E. 1.5.1 und 1.5.2). Es ist zudem unhaltbar, die entlastenden Zeugenaussagen unberücksichtigt zu lassen (E. 1.5.3). Die vorinstanzliche Beweiswürdigung ist im Ergebnis willkürlich und verletzt den Grundsatz "in dubio pro reo". Andere Beweismittel werden von der Vorinstanz nicht genannt. Das Bezirksgericht würdigte weitere Beweismittel (insbesondere zusätzliche Befragungen des Beschwerdeführers), welche ebenso wenig rechtsgenügende Hinweise für Täterschaft und Schuld zu liefern vermochten. Es ist deshalb davon abzusehen, die Sache zur ergänzenden Sachverhaltsfeststellung an die Vorinstanz zurückzuweisen. Die Vorinstanz wird den Beschwerdeführer von Schuld und Strafe freizusprechen haben.
Damit erübrigt es sich, die weiteren Rügen des Beschwerdeführers näher zu prüfen.
2.
Die Beschwerde ist gutzuheissen. Der angefochtene Entscheid ist aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Mit dem Entscheid in der Sache wird das Gesuch um aufschiebende Wirkung gegenstandslos.
Bei diesem Ausgang des Verfahrens sind keine Kosten aufzuerlegen (<ref-law>). Der Kanton Aargau hat dem Beschwerdeführer eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Das Urteil des Obergerichts des Kantons Aargau vom 4. November 2015 wird aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Aargau hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Aargau, Strafgericht, 1. Kammer, schriftlich mitgeteilt.
Lausanne, 27. Juni 2016
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Faga