Faits :
A.
Par jugement du 15 décembre 2015, le Tribunal correctionnel de l'arrondissement de La Broye et du Nord vaudois a condamné X._ pour instigation à escroquerie, tentative d'instigation à escroquerie et infraction à la Loi fédérale sur les étrangers à une peine privative de liberté de 20 mois, avec sursis pendant 5 ans. Il l'a en revanche libéré de l'accusation d'instigation à incendie intentionnel.
Par le même jugement, le Tribunal correctionnel a en outre condamné B._ pour complicité d'escroquerie et complicité de tentative d'escroquerie à une peine pécuniaire de 240 jours-amende à 30 fr., avec sursis pendant 2 ans. Il a également condamné A._ pour tentative d'escroquerie, complicité d'incendie intentionnel et violation grave de la Loi fédérale sur la circulation routière à une peine privative de liberté de 14 mois, avec sursis pendant 2 ans. Enfin, il a condamné C._ pour escroquerie à une peine privative de liberté de 14 mois, avec sursis pendant 2 ans.
B.
Statuant le 31 mai 2016, la Cour d'appel pénale du Tribunal cantonal du canton de Vaud a très partiellement admis l'appel interjeté par le ministère public contre ce jugement, en ce sens qu'elle a suspendu partiellement, durant un délai d'épreuve de cinq ans, l'exécution de la peine de X._ portant sur une durée de 14 mois, le solde de 6 mois étant ferme. L'appel joint formé par X._ ayant été rejeté, le jugement a été confirmé pour le surplus.
En substance, la cour cantonale a retenu les faits suivants.
B.a. Durant l'automne 2010, X._, ressortissant kosovar né en 1972, a entrepris des démarches en vue de vendre un véhicule de marque Volvo S60 qu'il conduisait au quotidien, mais qui avait été immatriculé et assuré au nom de son frère C._. Estimant insuffisant le montant proposé par les acheteurs potentiels, X._ en a parlé à son ami B._, en lui disant qu'il aurait tout intérêt à bouter le feu à sa voiture. B._ l'a alors pris au mot et lui a répondu qu'il était en mesure de mettre un tel plan à exécution. Ayant vécu à Saint-Priest (France), dans la banlieue lyonnaise, il y disposait de contacts et savait qu'il était relativement aisé de faire incendier une voiture à cet endroit.
Le 6 novembre 2010, B._ et C._ se sont rendus à Saint-Priest dans le but de mettre le plan à exécution. B._ était chargé de prendre contact avec les personnes susceptibles de mettre le feu au véhicule. Quant à C._, il devait entreprendre sur place et en temps utile les démarches nécessaires auprès de la police. Aucune rémunération n'avait été prévue en faveur des deux prénommés. Le même jour, le feu a été bouté à la Volvo S60 par une personne non identifiée pour une somme de 800 à 1'000 euros que X._ avait préalablement remise à B._. C._ s'est ensuite rendu au commissariat de police de Saint-Priest afin de déposer plainte.
Le lendemain, X._ a annoncé le sinistre à la société D._ SA. En sa qualité de preneur d'assurance, C._ a été indemnisé par la compagnie d'assurances à hauteur de 22'560 francs. Cette somme a ensuite été reversée en mains propres à X._.
B.b. Souhaitant changer son véhicule de marque Volvo S40, immatriculée au nom de son collègue de travail A._, X._ a repris contact avec B._ durant l'automne 2011. L'objectif était que ce dernier procède de la même manière que pour la voiture Volvo S60.
Le 19 novembre 2011, B._, X._ et A._ se sont rendus à Saint-Priest. Le véhicule Volvo S40 a été incendié le même jour par une connaissance non identifiée de B._ pour une somme d'environ 800 à 1'000 euros que X._ lui avait remise. L'incendie s'est propagé au véhicule de marque Renault Koleos de E._ qui, garé à côté du véhicule Volvo S40, a été endommagé.
Le même jour, A._ a déposé plainte au commissariat de police de Saint-Priest. Puis, de retour à son domicile de F._, il a appelé la société d'assurances D._ SA pour l'informer de la situation. La société d'assurances a toutefois refusé d'entrer en matière sur les prétentions formulées par A._, dès lors que ce dernier avait déclaré dans un protocole d'entretien établi à la suite du sinistre qu'il avait lui-même stationné le véhicule à Saint-Priest, portières verrouillées et fenêtres fermées, alors qu'en réalité la voiture avait été garée par B._, qui avait laissé volontairement une fenêtre ouverte afin de créer un appel d'air. En revanche, dans la mesure où l'incendie de la voiture Volvo S40 s'était propagé au véhicule de E._, la société d'assurances a indemnisé le propriétaire de ce véhicule pour son préjudice à hauteur de 7'700 fr. 40.
B.c. Entre février 2011 et juin 2015 à tout le moins, X._ a séjourné en Suisse alors qu'il ne disposait d'aucun titre de séjour et qu'une interdiction d'entrée en Suisse d'une durée indéterminée lui avait été notifiée en septembre 1999.
C.
Contre cet arrêt, le Ministère public central du canton de Vaud forme un recours en matière pénale au Tribunal fédéral (6B_1120/2016). Il conclut principalement à la réforme du jugement du 31 mai 2016 en ce sens que X._ est reconnu coupable non seulement d'instigation à escroquerie, de tentative d'instigation à escroquerie et d'infraction à la LEtr, mais également d'instigation à incendie intentionnel, X._ étant condamné à une peine privative de liberté de 32 mois ferme, sous déduction de la détention subie avant jugement. Subsidiairement, il conclut à l'annulation du jugement et au renvoi de la cause à cette autorité pour nouveau jugement dans le sens des considérants.
X._ dépose également un recours en matière pénale au Tribunal fédéral (6B_1127/2016). Il conclut, avec suite de frais et dépens, principalement à sa réforme en ce sens qu'un sursis complet lui est octroyé. Subsidiairement, il conclut à l'annulation du jugement, la cause étant renvoyée à cette autorité pour nouveau jugement dans le sens des considérants. Il sollicite en outre le bénéfice de l'assistance judiciaire.
Invité à se déterminer sur le recours du ministère public, X._ a conclu à son rejet. Quant à la cour cantonale, elle a renoncé à se déterminer et s'est référée aux considérants de sa décision.

Considérant en droit :
1.
Les deux recours, dirigés contre le même jugement, concernent le même complexe de faits et soulèvent des questions connexes. Il se justifie de les joindre et de statuer par une seule décision (<ref-law> et 24 PCF).
I. Recours du Ministère public (6B_1120/2016)
2.
2.1. La cour cantonale a considéré qu'en vertu du principe de la territorialité (<ref-law>), l'acte d'instigation d'incendie intentionnel reproché à l'intimé, commis en Suisse, ne pouvait pas faire l'objet d'une condamnation pénale par les autorités suisses, dès lors que c'était en France que les auteurs principaux avaient incendié les véhicules. Elle a fondé son raisonnement en se référant à la jurisprudence du Tribunal fédéral (cf. <ref-ruling>), selon laquelle un acte de participation accessoire, commis en Suisse, à une infraction commise à l'étranger ne relève pas de la compétence territoriale suisse.
Le recourant conteste la libération de l'intimé du chef de prévention d'instigation à incendie intentionnel et invoque à cet égard une violation des art. 3 et 8 CP. Il soutient que la jurisprudence du Tribunal fédéral, ancienne et largement critiquée par la doctrine, n'est plus en phase avec les réalités actuelles et nuit à l'efficacité de la justice dans un contexte d'augmentation de la criminalité transfrontalière. Il estime nécessaire une modification de la pratique, qui permettrait de fonder la compétence territoriale des autorités suisses en présence d'un acte d'instigation commis en Suisse, mais dont l'infraction principale est perpétrée à l'étranger.
2.2. Un changement de jurisprudence doit reposer sur des motifs sérieux et objectifs, lesquels, sous l'angle de la sécurité du droit, doivent être d'autant plus importants que la pratique considérée comme erronée, ou désormais inadaptée aux circonstances, est ancienne. Un changement ne se justifie que lorsque la solution nouvelle procède d'une meilleure compréhension du but de la loi, repose sur des circonstances de fait modifiées, ou répond à l'évolution des conceptions juridiques. Le motif sérieux et objectif d'un changement de jurisprudence peut notamment résulter d'une connaissance plus précise ou complète de la volonté du législateur (<ref-ruling> consid. 5.2 p. 3; <ref-ruling> consid. 5.5.1 p. 303; <ref-ruling> consid. 6.1 p. 313).
Il convient en l'espèce d'exposer en premier lieu les dispositions et les principes applicables (cf. consid. 2.3), avant de relever les motifs qui sous-tendent la jurisprudence actuelle (cf. consid. 2.4) puis d'examiner les critiques exprimées par la doctrine afin de déterminer si celles-ci justifient une modification de la pratique actuelle (cf. consid. 2.5-2.10).
2.3.
2.3.1. Aux termes de l'<ref-law>, le Code pénal suisse est applicable à quiconque commet un crime ou un délit en Suisse. Cette disposition consacre le principe de territorialité. Il s'agit du principe de base applicable en droit pénal international, selon lequel la compétence pour connaître d'une infraction ressortit à l'Etat sur le territoire duquel cette dernière a été commise (<ref-ruling> consid. 2b/bb p. 148 s.; <ref-ruling> consid. 3 p. 146). Il s'impose pour des motifs d'équité d'une part et d'économie de procédure d'autre part, car c'est au lieu de commission de l'infraction que l'administration des preuves est susceptible de fournir les résultats les plus probants (arrêt 6B_21/2009 du 19 mai 2009 consid. 1.1 et les références citées).
Selon l'<ref-law> (art. 7 aCP), un crime ou un délit est réputé commis tant au lieu où l'auteur a agi ou aurait dû agir qu'au lieu où le résultat s'est produit. Cette norme constitue un complément indispensable à l'<ref-law> puisqu'elle définit selon quels critères une infraction est réputée commise en Suisse. Indirectement, la disposition permet également de tracer la ligne de partage entre la compétence territoriale et les différentes formes de compétence extra-territoriale ancrées aux art. 4 à 7 CP (SABINE GLESS, Internationales Strafrecht, 2 e éd., p. 47; H ARARI/LINIGER GROS, in Commentaire romand, Code pénal I, n° 6 ss ad <ref-law>). Si l'<ref-law> évoque expressément la situation de l'auteur de l'infraction (al. 1) et précise où la tentative est réputée commise (al. 2), le Code pénal ne prévoit en revanche aucune disposition relative à la question du rattachement des actes de participation accessoire, tels que l'instigation et la complicité.
2.3.2. Est un instigateur celui qui, intentionnellement, décide autrui à commettre un crime ou un délit (<ref-law>). L'instigation consiste à susciter chez autrui la décision de commettre un acte déterminé. Il doit exister une relation de causalité entre le comportement incitatif de l'instigateur et la décision de l'instigué de commettre l'acte, bien qu'il ne soit pas nécessaire que l'instigateur ait dû vaincre la résistance de l'instigué. L'instigation implique une influence psychique ou intellectuelle directe sur la formation de la volonté d'autrui. Cette volonté peut être déterminée même chez celui qui est disposé à agir ou chez celui qui s'offre à accomplir un acte réprimé par le droit pénal et cela aussi longtemps que l'auteur ne s'est pas encore décidé à passer à l'action concrètement. L'instigation n'entre en revanche pas en considération si l'auteur de l'acte était déjà décidé à le commettre (<ref-ruling> consid. 2a p. 14 s.; arrêt 6B_1202/2017 du 23 mars 2018 consid. 3.2).
A l'instar de la complicité (<ref-law>), l'instigation caractérise une forme de participation accessoire, en ce sens que l'incrimination ne se fonde pas en soi sur l'acte que commet le complice ou l'instigateur lui-même, mais repose au contraire sur le caractère typique et illicite du comportement de l'auteur principal (<ref-ruling> consid. 2b p. 232; <ref-ruling> consid. 5d p. 4). L'instigation et la complicité ne constituent ainsi pas des infractions autonomes et ne se conçoivent qu'en relation avec une incrimination issue du Code pénal ou d'une autre loi fédérale. En ce sens, l'illicéité de l'acte de participation découle de l'illicéité de l'acte principal, raison pour laquelle il est évoqué dans ce contexte la notion d'accessoriété (BERNHARD STRÄULI, in Commentaire romand, Code pénal I, n° 136 ad intro. aux art. 24 à 27 CP; TRECHSEL/PIETH/JEAN-RICHARD, Schweizerisches Strafgesetzbuch, Praxiskommentar, 3e éd., n° 24 ad intro. ad <ref-law>; DONATSCH/TAG, Strafrecht I, Verbrechenslehre, 9e éd., p. 154).
2.4. Dans sa jurisprudence constante, le Tribunal fédéral a considéré que les actes de participation devaient être réputés avoir été commis au même endroit que l'infraction principale, le principe de la territorialité (<ref-law>) ne trouvant aucune application propre au participant. Cette approche a été justifiée par le fait que, si l'<ref-law> (art. 7 aCP) prend en considération le lieu où l'auteur a agi et où le résultat s'est produit, cette disposition ne fixe en revanche ni le lieu de la participation, ni celui où l'auteur principal a pris la décision d'agir ou s'y est préparé. Or, en raison de son caractère accessoire, la participation n'acquiert aucune signification propre, dans la mesure où elle ne fait que favoriser l'accomplissement des faits constituant l'infraction principale et le succès de celle-ci. La prise en considération du caractère accessoire des actes de participation concorde en outre avec la solution consacrée par le législateur en matière de for interne, qui, en cas de participation, se trouve au lieu d'exécution de l'acte principal (art. 349 aCP; actuellement : <ref-law>). Il serait par ailleurs inadéquat, en raison de l'étroite relation entre l'acte principal et la participation, de soustraire à la juridiction pénale suisse, conformément à l'<ref-law>, l'auteur qui a agi à l'étranger, mais qui prend sa décision et prépare l'infraction en Suisse, alors que l'on poursuivrait et punirait en revanche l'instigateur ou le complice qui aurait agi en Suisse, cela sans tenir compte de la question de savoir si l'infraction principale est ou non punissable à l'étranger (<ref-ruling> consid. 7b p. 86).
Nonobstant les critiques de la doctrine (cf. infra consid. 2.5) ainsi que la modification législative envisagée dans les années 1980 (cf. infra consid. 2.6.2), la jurisprudence a été maintenue (cf. notamment <ref-ruling> consid. 5 p. 304; arrêt 6B_123/2014 du 2 décembre 2014 consid. 2.3, non publié aux <ref-ruling>; arrêts 6B_597/2015 du 18 avril 2016 consid. 1.2.2; 6B_115/2014 du 5 août 2014 consid. 2.2.1; 6B_86/2009 du 29 octobre 2009 consid. 2.3; 6S.331/2001 du 16 octobre 2001 consid. 1b/bb).
2.5. Cette conception a été commentée et critiquée par la doctrine, qui se prononce pour une solution permettant de fonder la compétence territoriale en Suisse, y compris à l'égard de l'instigateur ou du complice agissant depuis la Suisse, dans le contexte d'une infraction entièrement perpétrée à l'étranger (HANS SCHULTZ, Die strafrechtliche Rechtsprechung des Bundesgerichts im Jahre 1978, RSJB 1979 p. 530; POPP/KESHELAVA, in Basler Kommentar, Strafrecht I, 3e éd., no 16 ad <ref-law>; T RECHSEL/PIETH/VEST, Schweizerisches Strafgesetzbuch, Praxiskommentar, 3e éd., no 8 ad <ref-law>; DUPUIS ET AL., Petit commentaire du Code pénal, 2e éd., n° 21 ad <ref-law>; JOSÉ HURTADO POZO, Droit pénal, Partie générale I, 2e éd., p. 136 s.; DONATSCH/TAG, op. cit., p. 54; DANIEL KOLLER, Cybersex, Die strafrechtliche Beurteilung von weicher und harter Pornographie im Internet unter Berücksichtigung der Gewaltdarstellungen, thèse, Zurich 2007, p. 403 s.; AUDE BICHOVSKY, in KUHN ET AL., La nouvelle partie générale du Code pénal suisse, 2006, p. 9 ss; CHRISTIAN SCHWARZENEGGER, Internet-Recht und Electronic Commerce Law, 2001, p. 346; ALEXANDRE DYENS, Territorialité et ubiquité en droit pénal international suisse, thèse, Lausanne, 2014, p. 235 ss; contra : KATIA VILLARD, La compétence territoriale du juge pénal suisse (art. 3 et 8 CP) : réflexions autour d'évolutions récentes, RPS 2017 p. 153 ss; LA MÊME, La compétence du juge pénal suisse à l'égard de l'infraction reprochée à l'entreprise, in Collection genevoise, 2017, p. 133 ss; SABINE GLESS, op. cit., p. 50; JEAN-LUC COLOMBINI, La prise en considération du droit étranger [pénal et extra-pénal] dans le jugement pénal, thèse, Lausanne 1983, p. 34 s.).
2.6.
2.6.1. Au-delà des motifs ayant fondé la solution retenue par le Tribunal fédéral, les critiques des auteurs se concentrent principalement sur des considérations de politique criminelle. Elles mettent ainsi en exergue le fait que la jurisprudence consacrée pourrait avoir pour conséquence de créer des conflits négatifs de juridictions, soit des cas dans lesquels aucun Etat ne revendique sa compétence pour connaître des actes délictueux commis par le participant accessoire.
Les auteurs déplorent à cet égard l'absence de disposition légale topique permettant de fonder le rattachement territorial des actes de participation accessoire, contrairement à la solution choisie par les législateurs allemand (§ 9 Abs. 2 D-StGB) et français (art. 113-5 CP-fr.), qui admettent, sous certaines conditions s'agissant du droit français, la compétence du juge national en présence d'un acte de participation commis sur leur territoire en vue de la réalisation d'une infraction perpétrée à l'étranger.
2.6.2. Il n'est pas établi que le législateur de 1937 avait la volonté d'inclure dans le Code pénal un rattachement indépendant en raison des actes de participation accomplis en Suisse. Le Message du Conseil fédéral relatif au projet de nouveau Code pénal suisse se limite à relever, à ce sujet, que "le Code pénal doit être applicable à toute personne qui commet un délit en Suisse, à toute personne qui commet à l'étranger un délit contre notre Etat ou notre défense nationale, ou contre un Suisse, enfin à tout Suisse qui commet à l'étranger un délit à raison duquel nous demandons son extradition" (FF 1918 IV 1, p. 9 s.). L'exposé des motifs relatif à l'avant-projet de code pénal suisse élaboré en 1893 (CARL STOOSS, Motive zu dem Vorentwurf eines Schweizerischen Strafgesetzbuches, Allgemeiner Teil, septembre 1893) ne fait non plus aucune référence quant à un éventuel rattachement en Suisse des actes de participation.
L'introduction d'une norme topique avait en revanche été envisagée dans le contexte de la révision de la partie générale du Code pénal. L'avant-projet de 1987 prévoyait ainsi de compléter la loi en proposant un nouveau chiffre 2 à l'art. 3 AP-CP 1987, dont la teneur était la suivante : " 2. Die Teilnahme an einer ausschliesslich im Ausland begangenen Haupttat ist nur strafbar, wenn die Haupttat und die Teilnahme auch nach dem Recht der Haupttat strafbar ist ". L'objectif de cette disposition était de dissiper les controverses que suscitait la conception retenue par le Tribunal fédéral et de codifier la solution majoritairement défendue en doctrine, à savoir admettre la compétence suisse sous réserve que l'infraction en cause soit également punissable au lieu où elle a été commise (cf. HANS SCHULTZ, Bericht und Vorentwurf zur Revision des Allgemeinen Teils und des Dritten Buches "Einführung und Anwendung des Gesetzes" des Schweizerischen Strafgesetzbuches, 1987, p. 11 ss).
Cette proposition n'a toutefois pas été retenue par la commission d'experts qui a rédigé l'avant-projet de 1993 (cf. Rapport concernant la révision de la Partie générale et du Troisième livre du Code pénal et concernant une Loi fédérale régissant la condition pénale des mineurs, Office fédéral de la justice, 1993, p. 16), qui comme le Conseil fédéral à sa suite, a considéré que la matière devait continuer à être réglée par voie jurisprudentielle (cf. Message du 21 septembre 1998 concernant la modification du code pénal suisse [dispositions générales, entrée en vigueur et application du code pénal] et du code pénal militaire ainsi qu'une loi fédérale régissant la condition pénale des mineurs, FF 1999 II 1787, p. 1798 s.).
2.6.3. Des auteurs en déduisent qu'en renonçant à préciser le texte légal et en laissant expressément au juge le soin de régler la question, le législateur a volontairement laissé subsister une lacune dans la loi, qu'il appartiendrait au juge de combler (cf. en ce sens POPP/ KELSHELAVA, op. cit., n° 16 ad <ref-law>; DYENS, op. cit., p. 236).
Nonobstant les critiques de la doctrine, une volonté du législateur tendant à la modification de la jurisprudence développée jusqu'alors ne peut être déduite de l'abandon de la solution envisagée par les auteurs de l'avant-projet de 1987. Il y a lieu de relever à cet égard que le législateur a expressément prévu un rattachement territorial indépendant des actes de participation accessoire dans le contexte particulier des dispositions pénales prévues par la loi du 21 mars 2003 sur l'énergie nucléaire (cf. <ref-law>; RS 732.1). On en déduit que, dans l'optique du législateur, l'introduction d'un tel rattachement pour l'ensemble du droit pénal ne serait susceptible d'intervenir que dans le cadre d'une modification législative.
2.7.
2.7.1. Parmi les auteurs cités ci-avant, certains reviennent sur la pertinence de prendre en considération le caractère accessoire des actes de participation pour réfuter tout rattachement indépendant des actes d'instigation ou de complicité au regard des art. 3 et 8 CP (cf. en particulier SCHULTZ, KOLLER, SCHWARZENEGGER, DYENS, loc. cit.). Dans la mesure où le caractère accessoire des actes de participation ne les prive pas d'une portée propre - l'instigation en particulier constituant l'acte sans lequel l'auteur principal n'aurait jamais agi -, il se justifie selon eux de faire abstraction du principe de l'accessoriété et d'assimiler à un acte au sens de l'<ref-law> le comportement par lequel l'instigateur encourage l'auteur principal à commettre une infraction, respectivement le comportement par lequel le complice apporte sa contribution à l'infraction.
2.7.2. Le lieu où l'auteur a agi ou aurait dû agir (<ref-law>) se définit comme le lieu où l'auteur est physiquement présent lorsqu'il réalise l'un des éléments constitutifs de l'infraction considérée (<ref-ruling> consid. 1c/aa p. 75 s.). En d'autres termes, pour que l'infraction soit punissable en Suisse, il faut que l'auteur réalise l'un des actes constitutifs sur le territoire suisse. En revanche, le lieu où il décide de commettre l'infraction ou le lieu où il réalise les actes préparatoires ne sont pas pertinents (<ref-ruling> consid. 1.1 p. 338; <ref-ruling> consid. 5.2 p. 209 s.; <ref-ruling> consid. 3c p. 253). Les actes préparatoires ne revêtent en effet une importance, sous l'angle de l'<ref-law>, que lorsqu'ils sont expressément réprimés par le biais d'une infraction indépendante, tels que les <ref-law> (actes préparatoires délictueux) et 19 al. 1 let. g LStup (art. 19 ch. 1 al. 6 aLStup; HARARI/LINIGER GROS, op. cit., n° 17 ad <ref-law>; URSULA CASSANI, Die Anwendbarkeit des schweizerischen Strafrechts auf internationale Wirtschaftsdelikte [Art. 3-7 StGB], RPS 1996 p. 237 ss, p. 245).
On déduit de ce qui précède que la notion d'acte contenue à l'<ref-law> doit être appréciée exclusivement au regard des éléments constitutifs décrits dans la norme pénale spéciale. Or, ceux-ci sont le fait de l'auteur principal et non de l'instigateur, dont l'activité survient, par essence, avant la réalisation des éléments constitutifs de l'infraction. Il en est de même, selon les cas, de la contribution du complice, qui peut également intervenir en amont de la commission de l'infraction. Dans la mesure où, comme on l'a vu, les actes préparatoires ne sont pas pertinents pour déterminer le lieu de l'acte commis par l'auteur principal, il ne se justifie pas de prévoir une solution différente pour le cas où ils auraient été accomplis par un participant accessoire.
Dans ce contexte, la proposition de faire abstraction du caractère accessoire des actes d'instigation et d'assimiler le comportement de l'instigateur à un acte de l'auteur au sens de l'<ref-law> n'est pas convaincante. Elle aurait de surcroît des répercussions indésirables. Ainsi, la reconnaissance de la compétence territoriale des autorités suisses sur la base de la localisation de l'acte d'instigation reviendrait à créer un régime différent selon qu'une infraction commise à l'étranger est perpétrée en commun ou non : le droit suisse s'appliquerait à l'égard de l'instigateur qui est intervenu en Suisse au stade des actes préparatoires, mais pas lorsque ceux-ci sont le fait de l'auteur principal (cf. en ce sens VILLARD, RPS 2017 p. 155).
2.8. Par ailleurs, une partie de la doctrine, même critique à l'égard de la pratique du Tribunal fédéral, relève que, pour être compatible avec le principe d'accessoriété des actes de participation, l'admission d'une compétence juridictionnelle au lieu où le participant accessoire a agi supposerait que l'acte principal soit également incriminé au lieu de commission de l'infraction (cf. HANS SCHULTZ, Die räumliche Geltung des schweizerischen Strafgesetzbuches nach der neueren Gerichtspraxis, in RPS 1957 pp. 306 ss, p. 312; CASSANI, op. cit., p. 247; DYENS, op. cit., p. 237 s.). Toutefois, l'introduction par voie jurisprudentielle de l'exigence du respect de la double incrimination paraît peu compatible avec le principe de la légalité, dans la mesure où une telle exigence ne saurait être déduite des art. 3 et 8 CP (cf. VILLARD, Collection genevoise, 2017, n° 388 p. 136).
On ne saurait en outre faire abstraction de la sanction prévue par le droit étranger pour l'infraction considérée et effectivement prononcée à l'encontre de l'auteur principal, alors même que, selon l'<ref-law>, l'instigateur encourt la peine applicable à l'auteur principal et que l'<ref-law> prévoit pour le complice une atténuation obligatoire de la peine. Même si, en fonction de la culpabilité de chacun, le participant accessoire est susceptible d'être puni plus lourdement que l'auteur principal, la peine prononcée à l'étranger à l'encontre de celui-ci ne saurait être ignorée du juge appelé à sanctionner le participant accessoire. Les remarques de VILLARD à ce sujet apparaissent pertinentes (cf. Collection genevoise, 2017, n° 385 p. 135 s.; cf. également COLOMBINI, op. cit., p. 35).
2.9. Il s'agit encore de déterminer si, pour éviter un conflit négatif de compétence, il se justifierait, comme le suggèrent certains auteurs, d'admettre, en présence d'un tel conflit, la punissabilité des participants accessoires lorsque des actes sont commis en Suisse en vue d'une infraction commise à l'étranger. En l'espèce, il n'est toutefois pas établi que l'on se trouve en présence d'un conflit négatif de compétence. En effet, si le recourant fonde notamment son argumentation sur le risque d'impunité induit par la jurisprudence, il souligne dans le même temps qu'il n'aurait "d'autre choix, en cas de rejet du recours, que de dénoncer l'intimé aux autorités françaises afin qu'il soit poursuivi pour instigation à incendie intentionnel" (cf. recours, p. 4). Cela étant, l'introduction d'une compétence juridictionnelle spécifique qui ne surviendrait que dans l'hypothèse d'un conflit négatif de compétence contreviendrait au principe de la légalité, à l'instar de ce qui a été observé ci-avant s'agissant de l'exigence de la double incrimination (cf. supra consid. 2.8).
2.10. Les motifs qui précèdent commandent de s'en tenir à la pratique actuelle, qui exclut sous l'angle du principe de la territorialité tout rattachement indépendant pour les actes d'instigation, en raison de leur caractère accessoire.
3.
En l'espèce, l'activité reprochée à l'intimé relativement à l'infraction d'incendie intentionnel consiste en le fait d'avoir eu, à deux reprises, l'idée de bouter volontairement le feu à son véhicule pour obtenir une indemnisation de l'assurance, d'en avoir discuté avec son ami B._ et d'avoir accepté la proposition faite par celui-ci de solliciter les contacts qu'il avait en France afin de mettre le plan à exécution.
S'il ressort de l'état de fait retenu par la cour cantonale (<ref-law>) que l'intimé a agi en Suisse, aucun élément constitutif de l'infraction d'incendie intentionnel n'a toutefois été réalisé sur le territoire suisse. De même, dès lors qu'au regard de l'<ref-law>, le lieu où la décision de commettre l'infraction a été prise par l'auteur n'est pas pertinent pour déterminer le lieu de commission de l'infraction, on ne saurait a fortiori y voir une circonstance de rattachement suffisante lorsque la décision émane de l'instigateur. Quant au résultat de l'infraction, il est survenu intégralement en France, de sorte que sous cet angle non plus, l'acte n'est pas punissable en Suisse.
Il s'ensuit que la cour cantonale n'a pas violé le droit fédéral en considérant qu'aucune circonstance de rattachement ne permettait en l'espèce de rendre punissable en Suisse l'instigation à incendie intentionnel reprochée à l'intimé.
4.
Au surplus, dès lors que le recourant, qui était l'accusateur public dans la présente affaire, ne soutient pas que les agissements de l'intimé seraient constitutifs d'actes préparatoires délictueux en relation avec l'infraction d'incendie intentionnel (cf. art. 260 bis al. 1 let. g CP), ni que l'intimé aurait dû être renvoyé en jugement pour ce chef de prévention, il n'y a pas lieu d'examiner la cause sous cet angle.
Par ailleurs, dans la mesure où les critiques du recourant quant à la peine infligée à l'intimé supposent la condamnation de celui-ci pour instigation à incendie intentionnel, celles-ci sont sans objet.
5.
Le recours du ministère public doit donc être rejeté. En conformité avec l'<ref-law>, le recourant ne peut se voir imposer des frais judiciaires. L'intimé, qui a été invité à se déterminer sur le recours, a droit à une indemnité de dépens, à la charge du canton de Vaud (<ref-law>).
II. Recours de X._
6.
Le recourant soutient qu'il doit bénéficier d'un sursis complet à l'exécution de sa peine privative de liberté de 20 mois.
6.1. Selon l'<ref-law>, le juge suspend en règle générale l'exécution d'une peine privative de liberté de deux ans au plus lorsqu'une peine ferme ne paraît pas nécessaire pour détourner l'auteur d'autres crimes ou délits. L'<ref-law> prévoit que le juge peut suspendre partiellement l'exécution d'une peine privative de liberté d'un an au moins et de trois ans au plus afin de tenir compte de façon appropriée de la faute de l'auteur.
Lorsque la durée de la peine privative de liberté se situe, comme en l'espèce, entre un et deux ans, permettant donc le choix entre le sursis complet (<ref-law>) et le sursis partiel (<ref-law>), l'octroi du sursis au sens de l'<ref-law> est la règle et le sursis partiel l'exception. Celui-ci ne doit être prononcé que si, sous l'angle de la prévention spéciale, l'octroi du sursis pour une partie de la peine ne peut se concevoir que moyennant exécution de l'autre partie. La situation est comparable à celle où il s'agit d'évaluer les perspectives d'amendement en cas de révocation du sursis. Lorsqu'il existe, notamment en raison de condamnations antérieures, de sérieux doutes sur les perspectives d'amendement de l'auteur, qui ne justifient cependant pas encore, à l'issue de l'appréciation de l'ensemble des circonstances, un pronostic concrètement défavorable, le tribunal peut accorder un sursis partiel au lieu du sursis total. On évite ainsi, dans les cas de pronostics très incertains, le dilemme du " tout ou rien ". Un pronostic défavorable, en revanche, exclut tant le sursis partiel que le sursis total (<ref-ruling> consid. 5.3.1 p. 10).
Selon la jurisprudence, les conditions subjectives auxquelles l'<ref-law> soumet l'octroi du sursis intégral s'appliquent également à l'octroi du sursis partiel (<ref-ruling> consid. 3.3 p. 277; <ref-ruling> consid. 5.3.1 p. 10). Pour formuler un pronostic sur l'amendement de l'auteur, le juge doit se livrer à une appréciation d'ensemble, tenant compte des circonstances de l'infraction, des antécédents de l'auteur, de sa réputation et de sa situation personnelle au moment du jugement, notamment de l'état d'esprit qu'il manifeste. Il doit tenir compte de tous les éléments propres à éclairer l'ensemble du caractère de l'accusé et ses chances d'amendement. Il ne peut accorder un poids particulier à certains critères et en négliger d'autres qui sont pertinents (<ref-ruling> consid. 2.1 p. 185 s.; <ref-ruling> consid. 4.2.1 p. 5). Le défaut de prise de conscience de la faute peut justifier un pronostic défavorable, car seul celui qui se repent de son acte mérite la confiance que l'on doit pouvoir accorder au condamné bénéficiant du sursis (arrêt 6B_682/2017 du 11 décembre 2017 consid. 3.1).
Le juge doit par ailleurs motiver sa décision de manière suffisante (cf. <ref-law>). Sa motivation doit permettre de vérifier s'il a tenu compte de tous les éléments pertinents et comment ils ont été appréciés (<ref-ruling> consid. 2.1 p. 185 s. et les références citées).
Dans l'émission du pronostic, le juge dispose d'un large pouvoir d'appréciation. Le Tribunal fédéral n'intervient que s'il en a abusé, notamment lorsqu'il a omis de tenir compte de critères pertinents et s'est fondé exclusivement sur les antécédents du condamné (<ref-ruling>40 consid. 4.2 p. 143; <ref-ruling> consid. 2.3 p. 204).
6.2. La cour cantonale a posé un pronostic mitigé s'agissant du comportement futur du recourant. Elle a ainsi relevé que l'absence totale de scrupules dont avait fait preuve le recourant, son implication dans deux cas distincts d'escroquerie à l'assurance et ses sept précédentes condamnations inscrites au casier judiciaire plaidaient en faveur d'un pronostic défavorable. Il fallait également relever en ce sens le fait qu'il avait agi durant les délais d'épreuve qui lui avaient été fixés en 2009 à l'occasion de deux précédentes condamnations. Cela étant, le remboursement du montant du dommage et l'absence de comportements répréhensibles depuis 2011 - à l'exception de l'infraction à la loi sur les étrangers - ne permettaient pas de retenir un pronostic entièrement défavorable, de sorte qu'il se justifiait de prononcer un sursis partiel, seule une partie de la peine de privation de liberté de 20 mois, portant sur 6 mois, devant être exécutée.
6.3. Le recourant ne tente pas de démontrer que la prise en considération de l'un ou l'autre de ces éléments d'appréciation n'aurait pas été pertinente. Il se plaint en revanche de ce que sa situation personnelle n'a pas été évoquée au moment d'établir le pronostic. A cet égard, il se prévaut du fait qu'il est marié depuis dix ans et qu'il est père de trois enfants en âge de scolarité, dont il subvient aux besoins en travaillant comme recycleur dans l'entreprise de démolition contrôlée par son épouse. Si la situation personnelle constitue un élément d'appréciation pertinent au moment d'établir un pronostic sur le comportement futur du condamné, celle-ci ne saurait toutefois être considérée en l'espèce comme un élément plaidant en faveur d'un pronostic favorable. On observe en effet que le recourant était déjà père lors de ses précédentes condamnations, survenues entre 2000 et 2011, et que cette circonstance ne l'a pas dissuadé de commettre de nouvelles infractions. Par ailleurs, s'il a été retenu que l'épouse du recourant et les enfants communs du couple devaient obtenir la nationalité suisse dès l'été 2016, tel n'était en revanche pas le cas du recourant, celui-ci ne disposant d'aucune autorisation de séjour en Suisse. Le recourant ne saurait donc plaider que la stabilité de sa situation personnelle serait compromise par la seule perspective de subir une peine privative de liberté de six mois.
De même, le recourant reproche à la cour cantonale de ne pas avoir pris en considération l'état d'esprit favorable ni les regrets qu'il a exprimés au moment du jugement et qui dénotaient une prise de conscience sincère. Le recourant perd de vue que la cour cantonale a déjà tenu compte, dans une large mesure, de son attitude constructive en retenant qu'il avait entrepris tout son possible pour rembourser, à raison de plusieurs milliers de francs, le dommage causé à la compagnie d'assurance lésée. Elle a en outre relevé, au stade de la fixation de la peine, les regrets exprimés par le recourant ainsi que sa bonne collaboration durant l'enquête (cf. jugement entrepris, p. 23). On en déduit toutefois que, pour les juges précédents, ces éléments ne justifiaient pas à eux seuls de retenir un pronostic entièrement favorable, au vu notamment des nombreux antécédents du recourant.
6.4. Le recourant soutient que la cour cantonale a mal apprécié certains critères lui ayant permis d'établir le pronostic. Il reproche ainsi à la cour cantonale d'avoir accordé une trop grande importance à ses "mauvais antécédents", dès lors qu'il s'agissait de sa première condamnation à une peine privative de liberté depuis 2000 et que la détention provisoire de plus d'un mois subie en 2012 avait eu un effet radical sur son comportement. Toutefois, dans la mesure où il a été condamné pénalement à sept reprises entre 2000 et 2011 notamment pour vol, violation de domicile et lésions corporelles simples qualifiées, on ne saurait considérer que la cour cantonale a abusé de son large pouvoir d'appréciation en estimant que les antécédents devaient être qualifiés de "mauvais" et qu'ils ne permettaient pas de conclure à un pronostic entièrement favorable. Au demeurant, le recourant, qui a été condamné pour avoir séjourné en Suisse sans autorisation de séjour jusqu'en 2015 à tout le moins, ne peut pas être suivi lorsqu'il prétend ne plus avoir commis d'infractions depuis 2011. Quand bien même tel aurait été le cas, l'absence de nouvelles infractions n'est d'aucune pertinence, dès lors qu'un tel comportement correspond à ce que l'on doit pouvoir attendre de tout un chacun (cf. arrêt 6B_1265/2016 du 26 octobre 2017 consid. 2.2 et les références citées).
Le recourant soutient par ailleurs qu'il est faux de retenir chez lui une "absence totale de scrupules", étant donné qu'il s'est repenti très vite après les faits et qu'il est passé aux aveux dès sa deuxième audition. On comprend toutefois que l'absence de scrupules mise en exergue par la cour cantonale renvoie à la commission des faits et non au comportement que le recourant a adopté en cours d'instruction. Or, la cour cantonale a retenu qu'il était à l'origine des deux affaires d'escroquerie à l'assurance et qu'il avait entraîné avec lui ses trois comparses, sans se préoccuper des conséquences de ses actes et dans un seul dessein de lucre (cf. jugement entrepris, p. 22). Sur la base de ce qui précède, la cour cantonale pouvait donc retenir que les circonstances de la commission des infractions influaient défavorablement le pronostic.
6.5. Il s'ensuit que la décision cantonale ne viole pas le droit fédéral en tant qu'elle retient un pronostic mitigé quant à l'évolution du comportement futur du recourant et refuse pour ce motif l'octroi d'un plein sursis.
6.6. Au surplus, c'est en vain que le recourant se prévaut d'une violation de l'<ref-law>. En effet, même si la motivation de la cour cantonale est relativement brève, il découle de ce qui précède qu'elle a suffisamment exposé les critères pertinents à prendre en considération et la manière dont ils devaient être appréciés.
7.
Il résulte de ce qui précède que le recours doit être rejeté. Le recours était voué à l'échec, de sorte que l'assistance judiciaire doit être refusée (<ref-law>). Les frais judiciaires, dont la quotité tiendra compte de la situation financière du recourant, sont mis à la charge de ce dernier (art. 65 al. 2 et 66 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Les causes 6B_1120/2016 et 6B_1127/2016 sont jointes.
2.
Le recours du Ministère public (6B_1120/2016) est rejeté.
3.
Il n'est pas perçu de frais judiciaires pour la procédure 6B_1120/2016.
4.
Le canton de Vaud versera à l'intimé X._ une indemnité de 1500 fr. à titre de dépens pour la procédure 6B_1120/2016 devant le Tribunal fédéral.
5.
Le recours de X._ (6B_1127/2016) est rejeté.
6.
La demande d'assistance judiciaire du recourant est rejetée.
7.
Des frais judiciaires pour la procédure 6B_1127/2016, arrêtés à 1200 fr., sont mis à la charge de X._.
8.
Le présent arrêt est communiqué aux parties et à la Cour d'appel pénale du Tribunal cantonal du canton de Vaud.
Lausanne, le 23 juillet 2018
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
Le Greffier : Tinguely