بنى مرين به تلمسان راند و بر آنجا مستولى شد . عثمان بن يغمراسن از امير ابو زكريا يارى طلبيد او نيز سپاه موحدين را به ياريش فرستاد . سپاه بنى مرين در ناحيه تدلس با آن روبرو گرديد و منهزم شدند و بسيارى از ايشان به قتل رسيدند و بقايايشان به بجايه بازگشتند . يوسف بن يعقوب سپاه بنى مرين را به سوى بجايه برد و سردارى آن به برادر خود ابو يحيى داد و اين بعد از آن بود كه عثمان بن سباع از صاحب بجايه رخ بر تافته و به نزد او آمده بود و او را به تصرف بجايه ترغيب كرده بود و از سوى سلطان اكرام فراوان ديده بود . آنگاه با او اين سپاه را به بجايه فرستاد . اينان بجايه را محاصره كردند و از آنجا به تا كرارت و بلاد سدويكش رفتند و در آن حدود دست به تاراج و كشتار زدند و زمين آن زير پاى خويش درنورديدند و نزد سلطان يوسف بن يعقوب در لشكرگاهش در تلمسان باز گرديدند .
سلطان ابو عصيده صاحب تونس ، چون خبر يافت كه امير ابو ذكريا به عثمان بن يغمراسن يارى رسانده است ، نزد يوسف بن يعقوب كه با آنان دشمنى داشت كس فرستاد و او را به تصرف بجايه و نواحى آن تحريض كرد . بار اول رسول ميان آن دو در اين باب ، رئيس الموحدين ابو عبد اللّه بن اكمازير بود سپس در سال 703 بار ديگر با هدايايى عظيم از جمله مقاديرى زين و شمشير و مهميزهاى زرين و مرصع به انواع ياقوت و ديگر گوهرها به سفارت نزد او رفت . در اين سفارت وزير الدوله ابو عبد اللّه بن برزيكن نيز همراه او بود . اينان از نزد يوسف بن يعقوب با هدايايى گران بازگشتند كه از جمله سيصد استر بود . ميان دو طرف نامههاى مودت آميز و هدايا رد و بدل مىشد . يوسف بن يعقوب در اين امور در پردهء تعريض با سلطان مكاتبت داشت و حال آنكه با رئيس موحدين ابو يحيى بن لحيانى تصريحا مكاتبت داشت . سپاهيان بنى مرين به نواحى بجايه در آمد و شد بودند . تا يوسف بن يعقوب - چنان كه در اخبارش خواهد آمد .
بمرد .
خبر از كشته شدن هداج و فتنهء كعوب و بيعت ايشان با ابو دبوس و سپس به خوارى افتادنشان
عربهاى كعوب از زمان قيام امير ابو حفص در دولت حفصيان صاحب عزت و جاه بودند و مورد توجه دولتيان . از اين رو مبانى قدرتشان استحكام يافت و رشد كردند و سرمست نعمت شدند و در اطراف و اكناف دست به شورش و فساد گشودند و راه كاروانيان بريدند و باغها ويران كردند و كشتزارها را تاراج نمودند . عامه را با آنان كينه افتاد و از اعمال ناپسندشان به جان آمدند . رئيس ايشان هداج بن عبيد در سال 705 به بلد در آمد . مردم به ديدهء انكار در او نگريستند و آهنگ جدال نمودند . هداج به مسجد آمد تا نماز جمعه بگزارد مردم اعتراض كردند كه چرا با كفش به مسجد داخل شده او گفت : من با كفش پاى به مجلس سلطان مىگذارم . مردم پس از نماز برجستند و او را كشتند و پيكرش را در كوچههاى شهر كشيدند .