However, there is apparently no evidence that the encounter ever took place. Here is a discussion by Dirk J. Struik, from his book A Concise History of Mathematics, Third Revised Edition, Dover, 1967, p. 129:
There exists a widely quoted story about Diderot and Euler according to which Euler, in a public debate in St. Petersburg, succeeded in embarrassing the freethinking Diderot by claiming to possess an algebraic demonstration of the existence of God: "Sir, (a+b^n)/n = x; hence God exists, answer please!" This is a good example of a bad historical anecdote, since the value of an anecdote about an historical person lies in its faculty to illustrate certain aspects of his character; this particular anecdote serves to obscure both the character of Diderot and of Euler, Diderot knew his mathematics and had written on involutes and probability, and no reason exists to think that the thoughtful Euler would have behaved in the asinine way indicated. The story seems to have been made up by the English mathematician De Morgan (1806-1871). See L. G. Krakeur and R. L. Krueger, Isis, Vol. 31 (1940), pp. 431-32; also Vol. 33 (1941), pp. 219-31. It is true that there was in the eighteenth century occasional talk about the probability of an algebraic demonstration of the existence of God; Maupertuis indulged in one, see Voltaire's Diatribe, Oeuvres, Vol. 41 (1821 ed.), pp. 19, 30. See also B. Brown, Amer. Math. Monthly, Vol. 49 (1944).
Thanks to Craig Fraser and Tom Archibald for pointing out this reference.