Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

3
votes
1answer
109 views

Finding covering system of congruences with prescribed moduli

Is there an algorithm (better than exhaustive search) that for a given list of moduli $m_i$ produces a list of residues $0\leq r_i<m_i$ such that $(m_i,r_i)$ is a covering system of congruences, or ...
2
votes
3answers
126 views

Existence of $x,y$ Satisfying Diophantine Equation

Let $a,b$ be positive integers. Prove that there exist positive integers $x,y$ such that $$ \dbinom{x+y}{2} = ax+by $$
6
votes
1answer
140 views

What is the largest possible length of a prime number?

Let $p$ be a prime number , set $f(p)=2p+1$ and define $f^n(p)=f\circ f\circ\cdots\circ f(p)$ composition by $f,$ $n$ times. And define length of $p$, $L(p)$ as maximum of $n$ such that $f^i(p)$ is ...
3
votes
1answer
92 views

Existence of a prime partition

I'm interested in finding out whether there exists a prime partition of a given positive integer $N>1$ such that the partition has specific number of parts. For instance, as given in another ...
6
votes
4answers
166 views

Prove that there is an integer $n$ such that $n^{1992}$ starts with $1992$ one's.

This was taken from an old Brazilian Mathematical Olympiad (1992). As the title says, we're supposed to prove that there is an integer $n$ such that $n^{1992}$ starts with $1992$ one's (in the ...
3
votes
2answers
58 views

$\pi(x)\leq \frac x{f(x)}$ for some unbounded function $f(x)$

Let $\pi(x)$ denote the number of primes $\le x$. Can one prove $$\pi(x)\leq \frac x{f(x)}$$ for some function $f(x)(x\gt0)$, and $f(x)$ is unbounded? Please do not refer to prime number ...
0
votes
1answer
116 views

If a set is a group of objects, then what is an object? [closed]

If a set is a group of objects, then what is an object? My best try at this is the following: An object is anything that we can discuss or think about, separately from everything else. It is not ...
1
vote
0answers
37 views

prove divisibility using prime factorization

If $d|x^2$ how to show that $d|x$ using prime factorization method? I can write $x={p_1}^{a_1}.{p_2}^{a_2}......{p_r}^{a_r} $ . Then $x^2={p_1}^{2a_1}.{p_2}^{2a_2}...{p_r}^{2a_r}$. If ...
5
votes
1answer
61 views

$\lim \{r^n\}$ exists, Is $r$ an integer?

$r\in\Bbb R$, $|r|\gt1$ and $\lim\limits_{n\to\infty}\{r^n\}$ exists. Can one conclude that $r$ is an integer? Here, $\{x\}=x-[x] $ is the fractional part of $x\in\Bbb R$ If $r\in\Bbb Q$, the ...
4
votes
1answer
90 views

Sum of Residues Modulo $p^2$.

Let $p$ be an odd prime. Prove that $$ \sum_{k = 1}^{p-1} k^{2p-1} \equiv \frac{p(p+1)}2 \pmod{p^2}$$
2
votes
0answers
44 views

Why is the Legendre symbol $(\frac a p)$ not defined if $p | a$ in some books?

Why is the Legendre symbol $(\frac a p)$ not defined if $p | a$ in some books ? In some textbooks I've come to notice that the legendre symbol $(\frac a p)$ is not defined if $p | a$, where $p$ ...
6
votes
2answers
930 views

Sum of sum of $k$th power of first $n$ natural numbers.

I was working on a problem which involves computation of $k$-th power of first $n$ natural numbers. Say $f(n) = 1^k+2^k+3^k+\cdots+n^k$ we can compute $f(n)$ by using Faulhaber's Triangle also by ...
4
votes
6answers
356 views

prove that $2^{15} - 2^3 $ divides $ a^{15} - a^3$

Prove that $$2^{15} - 2^3 $$ divides $$ a^{15} - a^3$$ for any integer $a$. Hint: $$ 2^{15} - 2^3 = 5\cdot7\cdot8\cdot9\cdot13$$
0
votes
1answer
66 views

Is the canonical decomposition of $1$ defined?

Is the canonical decomposition of $1$ defined ? Many theorem starts by: let $m$ be a positive integer with canonical decomposition $p_1^{e_1} \dots p_n^{e_n}$. Sometimes I don't see the proof ...
1
vote
4answers
66 views

How to show two integers are relatively prime?

Suppose $a$ and $b$ are positive integers. How do I show that $\frac{a}{\text{gcd}(a,b)}$ and $\frac{b}{\text{gcd}(a,b)}$ are relatively prime?
0
votes
1answer
32 views

For how many values of $a,b,c\in(1,2\ldots,p-1)$ does $p$ | $({a^2}-bc)$ where $p$ is an odd prime number

In a mock test for an entrance exam I am preparing for came the following question: Let $p$ be an odd prime number and $T_p$ be the following set of matrices $$ T_p= \left( ...
0
votes
3answers
77 views

Find primes $p_1,p_2,..,p_6$ such that $1+\prod_{i=1}^{6}p_i $is not prime

Show that if$$ p_1, p_2, p_3, p_4, p_5, p_6 $$are primes, then $$1+\prod_{i=1}^{6}p_i$$ is not necessarily prime by using a specic example.
1
vote
2answers
31 views

Why are the congruences $p^2-1 \equiv 0(\mod 8)$ and $p^e \equiv 1 + e(p-1) (\mod 4)$ for odd prime $p$ and $e \ge 1$ true?

Why are the congruences $p^2-1 \equiv 0(\mod 8)$ and $p^e \equiv 1 + e(p-1) (\mod 4)$ for odd prime $p$ and $e \ge 1$ true ? Suppose $p$ is an odd prime. I see easily that $p-1 \equiv 0 (\mod ...
0
votes
2answers
46 views

Difficulty in understanding the following problem

Find the positive integers $n$ with exactly $12$ divisors $1 = d_1 < d_2 < \cdots < d_{12} = n$ such that the divisor with index $d_4 - 1$ (that is, $d_{d_4 − 1}$) is $(d_1 + d_2 + d_4)d_8$. ...
0
votes
2answers
22 views

Suppose $a,b,m$ are integers and $(a,m) = 1$. Does $a \equiv b \pmod m \Rightarrow (b,m) = 1$?

Suppose $a,b,m$ are integers and $(a,m) = 1$. Does $a \equiv b \pmod m \Rightarrow (b,m) = 1$ ? I know the least residues of $a$ and $b$ are the same. And I know $$(m,a)=(a, a \mod m)$$, so the ...
1
vote
0answers
48 views

Miller-Rabin: proof the other implication

Let $p > 1$ be an integer and write $p-1=2^kq$ where $q$ is odd. Then for all $a\not\equiv0 \pmod p$ $$a^q = 1 \pmod p$$ or $$a^{2^rq} = -1 \pmod p,\quad 0 \leq r < k.$$ I basically need to ...
2
votes
1answer
536 views

Show that the converse of Fermats Little Theorem is false using a counter example.

Show that the converse of Fermat's little theorem is false using a counter example. Show that $$a^{561} \equiv a \pmod p$$ and hence that the converse of Fermat's little theorem is false???
0
votes
1answer
31 views

Is it true that for $p_j^{\alpha_j-1}(p_{j}-1)>2(3^{k-1})$ for some $j$?

Let $p_i$ $(1 \leq i \leq m)$ be primes such that $p_i < 2(3^{k-1})+1 $, where $k \in \mathbb{N}$. Let $a=p_1^{\alpha_1} \cdots p_m^{\alpha_m}$ for some $\alpha_i >0$. Let $a > 2 (3^k)$. Is ...
1
vote
2answers
97 views

How to show if $m$ and $n$ are coprime and $m-n$ is odd, then $(m^2-n^2)^2$, $(2mn)^2$, $(m^2+n^2)^2$ have a common factor?

We know that the Pythagorean triples can be generated by the Euclid's formula $a=m^2-n^2$, $b=2mn$, $c=m^2+n^2$ for any positive integers $m,n$ and $m>n$. I am trying to prove the statement: The ...
3
votes
3answers
127 views

Show how to compute $2^{343}$ using the least multiplication.

Show how to compute $2^{343}$ using the least multiplication.
0
votes
3answers
1k views

Difference between modulus and remainder

(I've come here from this question.) What's the difference between modulus and remainder? (Bearing in mind until 5 minutes ago I thought they were the same :P )
1
vote
3answers
98 views

Prove: for all integers $x,y\in x+y+xy = 0$ -> $x=y=0 $ or $ x=y=-2$

How would you do the proof for this problem? Prove that for all integers $x,y$, $(x+y+xy=0)\implies ((x=y=0)\vee(x=y=-2))$
0
votes
5answers
206 views

Prove that $4^n$ is not divisible by 3.

How can one prove that $4^n$ is not divisible by 3, for any $n \ge 0$? One way I found is to proof that $4^n - 1$ is always divisible by 3 (as demonstrated in a question here), thus $4^n$ could ...
21
votes
10answers
3k views

Shall remainder always be positive?

My cousin in grade 10, was told by his teacher that remainders are never negative. In a specific example, $$-48\mod{5} = 2$$ I kinda agree. But my grandpa insists that $$-48 \mod{5} = -3$$ Which ...
3
votes
2answers
372 views

Can be rational?

Can $z=\sqrt{1-4y^x}$ be a rational number, where $x>2$ is an integer and $y$ is a rational number and $y>0$? I have tried with $x=2$ and it has rational solutions, for example $y=12/25$ and ...
3
votes
3answers
560 views

recursive digit sum of cubes of integers.

For every cube of an integer, the recursive sum of its digits , e.g. 729 -> 18 -> 9 etc. is always 1,8 or 9. With a computer program i checked this phenomenon up to 1000000000. In my prior ...
2
votes
4answers
266 views

Find number x such that $x\equiv 4^{1002}\pmod{55}$

Find a natural number x, for $0 \le x \le 54$ such that is a solution for the following equation: $$x\equiv 4^{1002}\pmod{55}$$ This question was asked in an exam, so I expect that the answer is ...
0
votes
2answers
18 views

$P_k=[\frac{k-1}{m},\frac{k}{m})$, $k=1,\ldots,m.$, $q \in P_k$, prove that $nq \pmod 1 \in P_l$ for some $n \in \mathbb{N}$

I could not come up with a rigorous proof of the following fact, I'd be thankful if you could help me with this ( elementary) question. Consider a partition $\Gamma_m$ of $[0,1)$ by sets ...
0
votes
1answer
82 views

Existence of Integer Solutions

Prove that there exist integer solutions for the equation x^2 ≡ 251 mod 779. [Note that 779 = 19 · 41.] I know there are properties that can be used when both 251 and 779 are prime but I'm ...
1
vote
1answer
71 views

What is $|Aut(D_n,|)|$?

Let $n=p_1^{\alpha_1}\dots p_k^{\alpha_k}$ with the $p_i$ distinct primes and $ \alpha_i\in \Bbb N$. Just to check if I'm correct, is it true that $k!$ is the number of order-isomorphisms of the form ...
1
vote
1answer
48 views

What can we say about this quantity?

Let $\phi(n)$ be the Euler phi-function. If $a>1$ is an integer, then what is the remainder when $\phi(a^n - 1)$ is divided by $n$ in accordance with the Euclidean algorithm?
10
votes
3answers
89k views

What five odd integers have a sum of $30$?

I've been asked the following question: What five odd integers from the set $\{1, 3, 5, 7, 9, 11, 13, 15\}$ that when summed together equals to $30$? Note that any integer can be used more than ...
2
votes
2answers
76 views

Showing equality of primitive roots with quadratic non-residues.

Suppose that $p$ and $q = 2p + 1$ are both odd primes. Show that the $p − 1$ primitive roots of $q$ are precisely the quadratic non-residues of $q$, other than the quadratic non-residue $2p$ of ...
1
vote
1answer
15 views

Gauss' Lemma: $r_1, \ldots, r_k, p - s_1, \ldots, p-s_{\nu}$ are all incongruent where $r_i, s_j$ are least residues.

I'm having trouble understanding a step in the below proof of Gauss' Lemma. I see that $r_1, \ldots, r_k, p - s_1, \ldots, p-s_{\nu}$ are all less than $p/2$ and it follows that $r_1,\ldots, r_k$ ...
1
vote
1answer
37 views

Finding the Best Constant in Prime Counting Function Relation

How close can we approximate the best constant $c$ such that $n^{\pi(2n)- \pi(n)} \le c^n$ for all positive integers $n$. I know that $c = 4$ works from $n^{\pi(2n)-\pi(n)} < \prod_{n < p \le ...
0
votes
0answers
24 views

$n,k$-safe sequences.

Here, rah4927 asked a question equivalent to: Prove that you can choose numbers $a,b,c,d$ from a list of $131$ nonnegative integers less than $2^{13}$ such that $a\oplus b\oplus c \oplus d=0$. ...
2
votes
2answers
214 views

Second Course in Number Theory - Self Study

I just finished a first course in number theory using Dudley's Elementary Number Theory. This was by far my favorite math course and I want to learn more number theory this summer. As far as ...
3
votes
0answers
170 views

Conjecture on OEIS A167055

OEIS A167055 Numbers n such that $12n + 5$ is prime. $0, 1, 2, 3, 4, 7, 8, 9, 11, 12, 14, 16, 19, 21,...$ are items of OEIS A167055. I conjecture that the set of the sum of every two items of this ...
0
votes
1answer
53 views

Verify my proof on elementary number theory

I've tried to prove this theorem, which is very simple, but is a kind of practice for me. Let $a,b$ be two positive integers. Therefore, if $a+b$ is a composite number, $frac(\frac{a}{l}) + ...
0
votes
3answers
53 views

Equation involving power of two

I want to show that the equation $2^x - 1 = 3^y$ does not have any positive integer solutions except for $ x = 2 , y = 1$ . Is it possible to prove the assertion using binary representation of powers ...
1
vote
0answers
267 views

Vieta jumping with non-monic polynomials

I have recently discovered Vieta jumping as a problem-solving technique. In order to teach myself about it, I have located most (all of?) the standard references, both here on MSE and "out there" (via ...
1
vote
1answer
39 views

Polynomial that is surjective $\mod n$ for all $n$?

I was curious about an existence of the following polynomial $f(x) \in \mathbb{Z}[x]$ and $f(x) \not = x$ such that given any $n \in \mathbb{N}$, $f: \mathbb{Z} / n\mathbb{Z} \rightarrow \mathbb{Z} / ...
3
votes
2answers
159 views

How to show that $\displaystyle [a,b,c] = \frac{abc}{(ab,bc,ca)}$ without prime factorization?

I think this has been asked before, but I couldn't find it on math.SE. I googled it too, but I wasn't lucky enough to find it there either. So, here's the problem: Demonstrate that for any $a,b,c \in ...
1
vote
3answers
108 views

Help needed in understanding proof: Every odd prime $p$ has exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues.

Help needed in understanding proof: Every odd prime $p$ has exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues. We assume there exist $k$ incongruent quadratic residues and ...
1
vote
2answers
109 views

Hard elementary-number-theory question on solve all $n$s that make $2^6+2^{10}+2^n$ a square numbe

I want to know all the nonnegative integer $n$ that makes $2^6+2^{10}+2^n$ be some other integer's square. I have tried it numerically for a range from $0$ to $1000$, and only $0,9,11,12,15$ returns ...