Gemara

(Mishnah): If two women were captured and each says 'I was captured but I am Tehorah', they are not believed;

If each testifies that the other is Tehorah, they are believed.

(Mishnah): Similarly, if each of two men says 'I am a Kohen', they are not believed. If they also testify about each other, they are believed;

24a: When two women were captured and testify about each other, one might have thought that we should suspect that they are Gomlin (conspiring to help each other). The Mishnah teaches that this is not so.

(Beraisa): If Reuven said 'I am a Kohen, and so is David', we rely on him to let David eat Terumah, but not regarding lineage (for David to marry);

If a third man is with them, and each Kohen has two others testifying that he is a Kohen, this establishes them to have proper lineage;

R. Yehudah says, even regarding Terumah Reuven is not believed unless there is a third man.

Contradiction: Elsewhere, R. Yehudah is not concerned lest two lie to help each other, and Chachamim are concerned for this!

(Mishnah): If two merchants (Levi and Shimon) entered a city, and Levi said 'my produce is new and Shimon's is old. Mine is Tevel and Shimon's is tithed', he is not believed;

R. Yehudah says, he is believed.

Answer #1 (Rav Ada bar Ahavah): The opinions (in the Beraisa) must be switched.

Answer #2, part 1 (Abaye): R. Yehudah is lenient regarding Demai (doubtfully tithed produce), because most people tithe.

Answer #2, part 2 (Rava): We resolve the contradiction in Chachamim like Rav Chama answered (elsewhere), 'this is when he is holding tools of the trade.

Answer #3: R. Yehudah and Chachamim argue about whether or not we establish a person to have proper lineage based on seeing him eat Terumah. (R. Yehudah says that we do, so he always requires two witnesses to establish a person to be a Kohen to eat Terumah. However, in a case where one witness suffices, he is not concerned lest two conspire to testify falsely for each other.)

Mishnah (Demai 4:6): If David entered a city and asked who is trustworthy and tithes, Yakov is not believed to say 'I am'. If Yakov said 'Moshe is', and David bought from Moshe and asked who sells old produce and Moshe said 'Yakov does', even though it looks like they are Gomlin, they are believed.

Rishonim

The Rif and Rosh (2:28) bring the Mishnayos.

Ran (DH Masnisin): We are not concerned lest Leah testifies for Chanah in order that Chanah will testify for Leah. Two Kohanim who testify about each other are believed, and we give to them Terumah.

Rambam (Hilchos Isurei Bi'ah 18:17): If two captured women testify for each other, they are believed. This is because the Isur of all Sefekos is mid'Rabanan, therefore Chachamim were lenient about a Shevuyah.

Rambam (20:11): If each of two men says 'we are Kohanim', even though it looks like they are Gomlin, they are believed, and we establish them to be Kohanim.

Question (Ramach): Why did the Rambam omit that they are believed only to give to them Terumah, but not for lineage? No one argues about this!

Rambam (Hilchos Ma'aser 12:10): If merchants (Levi and Shimon) entered a city, and Levi said 'my produce is Tevel and Shimon's is tithed', he is not believed. Perhaps they scheme, and plan to share the profits.

Question (Radvaz): Why are we not concerned for Gomlin in the Reisha (Demai 4:6)? The Rambam answered this by saying that it is a scheme. In the Reisha, they are not likely to benefit each other (Yakov did not know that David would ask Moshe who sells old produce).

Ri Korkus and Kesef Mishneh: The Rambam does not bring the Gemara's answer, that here he is holding tools of the trade. Rashi explained that we suspect merchants of Gomlin when the one who degrades his produce is holding a stick used to even off measures, for this shows that he intends to sell. The Rambam explains like R. Chananel, that 'he is holding tools of the trade' refers to the Mishnah of Kohanim. We believe that they are Kohanim when they have special Kelim, e.g. of dung, which are not Mekabel Tum'ah. In Hilchos Isurei Bi'ah, the Rambam did not make this stipulation. Therefore, it seems that the Rambam holds that once we answered that R. Yehudah and Chachamim argue about establishing lineage based on Terumah, we no longer need to say that he is holding tools of the trade. Alternatively, we do not establish the case to be when he is holding tools of the trade. Rather, merchants generally come to sell, so the scheme is evident.

Question (Tosfos Yom Tov Kesuvos 2:8 DH R. Yehudah): The Kesef Mishneh did not explain how we resolve the contradiction in Chachamim by saying that they argue about establishing lineage based on Terumah. Perhaps Chachamim are stringent (to be concerned for Gomlin) regarding merchants, for this does not cause a loss to them; they can sell in the next city. Chachamim are lenient about Kohanim, lest they lose, i.e. they will need to buy Chulin, which costs more than Terumah. However, if so we must say that they discuss Terumah mid'Rabanan, for the Rambam (Isurei Bi'ah 20:4) establishes lineage based on Terumah mid'Oraisa. However, the Gemara connotes that we discuss Terumah mid'Oraisa; this is clear to the Ran. I cannot resolve the contradictions between Perush ha'Mishnayos and the Mishnah Torah about establishing lineage from eating or receiving Terumah.

Beis Meir (EH 3:4): Tosfos concludes that we resolve the contradiction even in Chachamim by saying that they argue about establishing lineage based on Terumah. This is according to Rashi. According to R. Chananel, we are lenient about Kohanim only when they hold special Kelim. This does not explain why we are lenient about Shevuyos! R. Chananel must explain that we are lenient about mid'Rabanan laws, including Terumah mid'Rabanan. We require special Kelim only for Terumah mid'Oraisa.

Radvaz (Teshuvah 5:116): The Rambam says that we are not concerned even when it looks like they are Gomlin. R. Yehudah and Chachamim argue about when they are truly Gomlin. The final answer, that they argue about establishing lineage based on Terumah, resolves R. Yehudah. To explain Chachamim we must say that we are stringent about Ma'aser when he holds the tools of the trade, for then the scheme is evident.

Rosh (Gitin 5:8:5): If merchants (Levi and Shimon) entered a city, and Levi says 'my produce is not tithed, but Shimon's is tithed, they are not believed, for we are concerned for Gomlin.

Rosh (5:12:10): If two men both say 'we are Kohanim', they are not believed if there is concern for Gomlin. A merchant is not believed to say that his produce is tithed, even if someone else confirms this, when we are concerned for Gomlin.

Poskim

Shulchan Aruch (EH 3:4): Even if two men come and each testifies about the other that he is a Kohen, they are believed, and we are not concerned for Gomlin.

Gra (21): This is like Rashi, unlike R. Chananel who says that even R. Yehudah agrees.

Shulchan Aruch (7:1): If two Shevuyos testify for each other, they are believed.