Feladat: B.4326 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Dolgos Tamás 
Füzet: 2012/október, 416. oldal  PDF file
Témakör(ök): Diofantikus egyenletek, Feladat, Számelmélet, Teljes indukció módszere
Hivatkozás(ok):Feladatok: 2011/január: B.4326

Legyenek a és b egész számok. Adjunk meg olyan c és d egészeket, amelyekre tetszőleges n egész szám esetén az an+c relatív prím bn+d-hez.

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

 
Megoldás. Ha a=b=0, akkor például c=d=1 megfelelő választás. A továbbiakban feltesszük, hogy a és b közül legalább az egyik nem 0, ekkor jelölje d a két szám legnagyobb közös osztóját. Legyen a=da', b=db', ahol a' és b' egymáshoz relatív prím egész számok. Felhasználjuk azt a jól ismert számelméleti összefüggést, amely szerint az
ux+vy=m(u,v,mZ)
diofantikus egyenletnek pontosan akkor van megoldása, ha (u,v)m. Ezt az állítást a b'x-a'y=1 egyenletre alkalmazva kapjuk, hogy léteznek olyan c és d egész számok, amelyekre b'c-a'd=1. Ezzel a választással an+c és bn+d az n tetszőleges egész értéke esetén relatív prímek, hiszen az alábbi összefüggésből kiderül, hogy minden közös osztójuk osztja az 1-et is:
b'(an+c)-a'(bn+d)=(b'da'-a'db')n+(b'c-a'd)=1.
Ezzel megmutattuk, hogy léteznek a feladat feltételét kielégítő c és d egész számok.