I'm a new to modular maths and I need to find 'a' given $(x+y)^p \equiv a^b+c^d\pmod p$

I'm new to modular maths and I've been asked to do the following:

given p is prime and $(x+y)^p \equiv a^b+c^d\pmod p$ , find a=?,b=?,c=?,d=?

Can anyone help me with the same? Or atleast point me in the right direction? Or give me a solution for the same?

Thanks.

[UPDATE 1] Using congruence property and then fermat's little theorem, i was able to get to: $(x+y)^p \pmod p \equiv a^b+c^d$

$(x+y) \pmod p \equiv a^b+c^d$

which means that : $(x+y) = a^b+c^d$ (am I on the right path?)

[UPDATE 2]

I've got to:

$(x+y) \pmod p \equiv a^b+c^d$, which can be written as

$x \pmod p \equiv a^b$

$y \pmod p \equiv c^d$

• I may be very stupid, but I fail to see how one can find four numbers given only their value $a^b+c^d$ modulo $p$. Say $x+y=1$ and $p=3$, and even knowing that $a,b,c,d$ are only determined modulo $p$, that still leaves a lot of possibilities, for example if $a=0$, $c$ can be $1$ and $d$ arbitrary (meaning, $0, 1, 2$), or $c=2$ and $d=0$ or $d=2$ works. – ForgotALot Mar 18 '16 at 3:17
• @ForgotALot, I'm looking to express a,b,c,d in terms of x and/or y – ReubenCH Mar 18 '16 at 3:34
• This is not what the spirit of the exercise requires, but $d=p$, $c=0$ and $a = x+y$ will certainly work :) – PhoemueX Mar 18 '16 at 5:11
• @PhoemueX could explain how you achieved that? – ReubenCH Mar 18 '16 at 6:00
• Okay, you got to $x+y \equiv a^b+c^d \bmod p$. What’s wrong with $(a, b, c, d) = (x, 1, y, 1)$? – Lynn Mar 18 '16 at 10:40

Binomial coefficients

You may know these formulas:

\begin{align*} (a+b)^2 &= a^2 + 2ab + b^2 \\ (a+b)^3 &= a^3 + 3a^2b + 3ab^2 + b^3 \\ (a+b)^4 &= a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4 \\ \text{etc.} \end{align*}

Each term in the expansion of $(a+b)^n$ clearly has the form $c \cdot a^k b^{n-k}$, where the coefficient $c$ arises from the number of different ways you can choose $k$ copies of $a$ and $(n-k)$ copies of $b$ in the product:

$$\underbrace{(\color{brown}a+\color{teal}b)(\color{brown}a+\color{teal}b)\dots(\color{brown}a+\color{teal}b)}_{\text{n times}}.$$

For example, for $n=4$ and $k=2$, there are six choices:

$$\color{brown}{aa}\color{teal}{bb}+\color{brown}a\color{teal}b\color{brown}a\color{teal}b + \color{brown}a\color{teal}{bb}\color{brown}a+\color{teal}b\color{brown}{aa}\color{teal}b + \color{teal}b\color{brown}a\color{teal}b\color{brown}a + \color{teal}{bb}\color{brown}{aa} = 6\color{brown}a^2\color{teal}b^2.$$

We call $6$ “the binomial coefficient $\binom 42$”.

Computing $\binom nk$

We can count the number of anagrams of $a^k b^{n-k}$, by saying:

• We count all $n!$ permutations of the string $a^k b^{n-k}.$

• But now we will have counted each possible string $k! (n-k)!$ times: once for each possible choice of both

• a permutation of the $k$ occurences of $a$, and

• a permutation of the $(n-k)$ occurences of $b$.

(That is, shuffling the $a$s among themselves, and shuffling the $b$s among themselves, does not actually give us distinct strings.)

If we count $n!$ strings when counting each string $k! (n-k)!$ times, then there must be $$\binom nk=\frac{n!}{k!(n-k)!} \textbf{ distinct}\textrm{ strings}.$$

The binomial formula

We can now write, in general:

$$(a+b)^n = \sum_{k=0}^n \binom nk a^k b^{n-k}.$$

For which $k$ is $\binom pk$ a multiple of $p$?

The fraction looks like this:

$$\binom pk = \frac{p!}{k!(p-k)!} = \frac{1 \cdot 2 \cdot (\ldots) \cdot k \cdot (k+1) \cdot (\ldots) \cdot p}{1 \cdot 2 \cdot (\ldots) \cdot k \cdot 1 \cdot (\ldots) \cdot (p-k)}.$$

We know that $0 \leq k \leq p$. (That is the range we take the sum over.)

We also know that $\binom pk$ must be an integer.

There is a term $p$ in the numerator: if we can’t cancel it out somehow, the fraction will be a multiple of $p$.

But since $p$ is a prime, dividing by any number in $\{1, \dots, p-1\}$ can’t harm the $p$ on top. Thus, we need a $p$ in the denominator to cancel out the $p$.

The terms in the denominator range from $1$ to $k$; and then, from $1$ to $p-k$. Thus, we can cancel out the $p$ precisely when $k=p$ or $p-k=p$ (i.e. $k=0$). In all other cases ($1 \leq k \leq p-1$), the binomial coefficient will be a multiple of $p$!

That means, working modulo $p$, all of the terms $1 \leq k \leq p-1$ will vanish, and we get:

$$(a+b)^p = \sum_{k=0}^p \binom nk a^k b^{p-k} \equiv a^0 b^{p-0} + a^p b^{p-p} = a^p + b^p \pmod p.$$

• Thank you for the explaination! I'm still trying to figure out what to do with x & y? – ReubenCH Mar 18 '16 at 12:23