1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ForgotALot Mar 18 '16 at 3:17
  • $\begingroup$ @ForgotALot, I'm looking to express a,b,c,d in terms of x and/or y $\endgroup$ – ReubenCH Mar 18 '16 at 3:34
  • $\begingroup$ This is not what the spirit of the exercise requires, but $d=p$, $c=0$ and $a = x+y$ will certainly work :) $\endgroup$ – PhoemueX Mar 18 '16 at 5:11
  • $\begingroup$ @PhoemueX could explain how you achieved that? $\endgroup$ – ReubenCH Mar 18 '16 at 6:00
  • $\begingroup$ 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)$? $\endgroup$ – Lynn Mar 18 '16 at 10:40
2
$\begingroup$

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.$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.