2
$\begingroup$

Let $N$ be any integer and $B \geq 2$ be a smoothness bound. Does there always exist $B$-smooth integers $x,y$ such that: $$x + y \equiv 0 \pmod{N}\text{ ?}$$

My only progress is that I know the question reduces to the case $B=2$ and I can guess-and-check to find solutions for various $N$. For example: $$N=5,\ x=128,\ y=-8$$ $$N=13,\ x=1024,\ y=16\text{.}$$

But this does nothing to prove or disprove the statement in general. I don't expect anyone to do the work for me. But I was curious whether there is a known result on this already, or perhaps if the answer is obvious.

For the rational sieve it's apparently not necessary that the smooth pairs $x,y$ be a sum or difference of $N$; prime multiples of $N$ seem to work too. And I was curious whether this weaker condition would allow $B$ to be arbitrarily small.

$\endgroup$
0
$\begingroup$

I'll answer my own question with what I've discovered. This is not even close to a proof but is sufficient for my application.

To show that for any $N,B$ there exists B-smooth $x,y$ such that $x + y \equiv 0\pmod{N}$, it's sufficient to show this for the case $B=2$.

Let $B=2$. There are four possible cases for $x,y$:

  1. $x>0,\ y>0$.
  2. $x>0,\ y<0$.
  3. $x<0,\ y>0$: the result for this case follows from case 2, since $x,y$ are just flipped here.
  4. $x<0,\ y<0$: the result for this case follows from case 1 taken for $-N$.

For the first case, we write $2^a + 2^b \equiv 0 \pmod{N}$ and let $b$ denote the greater of $a,b$. Then $$0 \equiv \frac{0}{\gcd(2^a, 2^b)} \equiv \frac{2^a + 2^b}{\gcd(2^a, 2^b)} \equiv 2^{b-a} + 1 \equiv 2^k + 1 \pmod{N}\text{.}$$ So, $$\exists\ x,y,\ x + y \equiv 0 \pmod{N} \iff \exists\ k,\ 2^k \equiv -1 \pmod{N}\text{.}$$ But modular exponentiation is cyclic, so it's easy to provide a counterexample, namely $N=35$: $$\begin{array}{l|lllllllllllllllll} k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & \dots \\ \hline 2^k \pmod{35} & 1 & 2 & 4 & 8 & 16 & 32 & 29 & 23 & 11 & 22 & 9 & 18 & 1 & 2 & 4 & 8 & \dots \end{array}$$

For the second case, using the method from case 1 we just need to show $\exists\ k,\ 2^k \equiv 1 \pmod{N}$. If $N$ is odd and square-free, then we can take $$k = (p_1 - 1)(p_2 - 1)\dots (p_n - 1)\text{,}$$ where $p_i$ are the $n$ prime factors of $N$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have no idea why that $k$ works when $N$ is odd and square-free. $\endgroup$ – user253804 Aug 5 '15 at 1:20

Your Answer

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