Angenommen ich habe folgende Fragestellung "11^49 + 4^49 teilbar durch 15"?

Wie kann ich hier am besten vorgehen um das zu beweisen, jedoch ohne Hilfsmittel wie Taschenrechner oder Onlinerechner.

Als Sprache habe ich nur einen Buchstaben zur Verfügung (z.b.: x). Wenn ich jetzt eingebe "xxx" oder "xxxxx" dann soll der Automat diese Eingabe akzeptieren, weil im ersteren Fall die Länge 3 ist und im zweiteren die Länge der Eingabe 5 ist. Und da die Länge durch 3 oder 5 teilbar sein sollte, sollte diese akzeptiert werden.

Allerdings komme ich nach stundenlangen Nachdenken nicht zu der Lösung. Kann mir da jemand helfen bitte?