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

learn more… | top users | synonyms (1)

2
votes
0answers
35 views

Legendre symbol identity

I try to solve the following problems ($p$ is an odd prime) Find the sum $$\sum_{a=1}^{p-1}a \cdot \left (\frac{a}{p} \right)$$ Find the sum $$\sum_{a=1}^{p-1} 2^a \cdot \left (\frac{a}{p} \right)$$ ...
2
votes
0answers
53 views

A false conjecture by de Polignac

(This question would be similar to my other on Goldbach's conjecture so I'll change the "rules") In 1848 de Polignac claimed that "every odd integer is the sum of a prime $p$ and a power of $2$". For ...
0
votes
3answers
43 views

Prove that the only numbers not expressible as a sum of consecutive positive integers takes the form $2^n$ for some $n \in \mathbb N$

I am trying to prove the above question. As I see it this is the statement that needs to be proved: a number $x$ has no odd factors $\iff$ $x$ cannot be formed by a sum of consecutive natural numbers. ...
0
votes
5answers
63 views

Prove or disprove that the difference of the squares of two odd numbers is always divisible by 4

Prove or disprove that the difference of the squares of two odd numbers is always divisible by 4. No idea how to use the proving method to solve this.
1
vote
0answers
94 views
+50

Conjectured primality test for specific class of $N=k\cdot 6^n-1$

How to prove that this conjecture is true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ~\text{and}~ x ...
0
votes
1answer
48 views

Proving well-ordering property of natural numbers without induction principle?

In Munkres, Topology, he has this way of proving the well ordering property for the natural numbers: He assumes he can work with the real numbers from the for the real numbers Then he defines an ...
1
vote
3answers
37 views

Product of first $n$-th prime power integers $+ 1$

I was just playing with prime numbers and then I accidentally found this pattern. Let $p_1\cdot p_2\cdot p_3\cdots p_n$ is the product of first $n$-th prime power integers. Prove that: $p_1\cdot ...
1
vote
1answer
29 views

Find the maximum value of the quotient

Given a real number $x,$ let $\lfloor x \rfloor$ denote the greatest integer less than or equal to $x.$ For a certain integer $k,$ there are exactly $70$ positive integers $n_{1}, n_{2}, \ldots, ...
-1
votes
1answer
29 views

50th smallest positive integer with sum of power of 3 [on hold]

Find the 50th smallest positive integer that can be written in the form of sum of distinct power of 3 with non-negative integer coefficient?
1
vote
1answer
25 views

Sum of digits of polynomial smaller than of factorial

I'm trying to prove this : Let $f \in Z[X]$ then for sufficiently large $n$ we have $$s(f(n))<s(n!)$$ where $s$ is the sum of digits function. What I have so far : I thought this must be true ...
2
votes
1answer
45 views

Sum of digits modulo a polynomial

I made the following problems a while ago but I can't solve them (though I don't think it's too hard) 1.Let $s(n)$ be the digits sum of $n$. Let also $f(n)$, $g(n)$ $\in Z[X]$ . Assume that: ...
3
votes
1answer
25 views

Simple congruence relation (modular arithmetic)

Let $p \neq 2,5$ be prime. Suppose you know that $p \equiv 1 \mod 4$ and that $(\frac{p}{5}) = 1$, with $(\cdot)$ the Legendre Symbol. How does it follow that $p \equiv 1 \mod 20 $ or that $p \equiv ...
0
votes
2answers
35 views

Find whole numbers $x$ and $y$ such that $61=9x+15y$

Do whole numbers $x$ and $y$ exist so 61 can be written in the form $61=9x+15y$? My book just covered Bezout's identity. How can I use it to find out if the coefficients exist?
0
votes
1answer
20 views

If $\text{gcd}(a,561)=1$, then $a^{560}=1\mod 561$ [duplicate]

We have the factorization $561=3*11*17$. Because $\text{gcd}(a,561)=1$, there are integers $x,y$ such that $ax+561y=1$. So $ax=1\mod 561$. Since the gcd is $1$, we have $a\not \in 3\mathbb{Z}, ...
0
votes
3answers
111 views

Proof that there are infinitely many prime numbers

I answered a question to prove that there are infinitely many prime numbers, but I'm not sure if my attempt is right. Can somebody help me to check if my attempt is right? I would like, if I am wrong, ...
3
votes
2answers
55 views

Does there exist integer such that there exist sum of powers congruent mod $p$?

Let $n \in \mathbb{N}$, $p$ prime. For arbitrary $C \in \mathbb{Z}$, does there exist $a_1, a_2, \dots, a_n \in \mathbb{Z}$ such that$$C \equiv \sum_{i=1}^n a_i^n \text{ }(\text{mod }p)?$$
19
votes
12answers
670 views

Which is greater, $98^{99} $ or $ 99^{98}$?

Which is greater, $98^{99} $ or $ 99^{98}$? What is the easiest method to do this which can be explained to someone in junior school i.e. without using log tables. I don't think there is an ...
0
votes
0answers
69 views

$(\mathbb Z /n\mathbb Z)^*$ is cyclic for all $n$ implies every finite abelian group is cyclic. [closed]

Show that, if $(\mathbb Z / n\mathbb Z)^*$ is cyclic for all $n \ge 1$ then every finite abelian group is cyclic. More precisely, prove that the following are equivalent: 1) $(\mathbb Z / n\mathbb ...
1
vote
2answers
61 views

$2017^{2016^{2015}} \mod 1000$

I'm trying to solve the following exercise: $$2017^{2016^{2015}} \mod 1000,$$ here's what I've already come up with: Using Euler's conrgruence, one finds that $$2017^{2016^{2015}} \equiv ...
1
vote
4answers
59 views

Showing $7n + 4$ and $5n + 3$ are coprime for all $n$

I am trying to show that $7n + 4$ and $5n + 3$ are coprime for all $n \in \mathbb Z$ but I'm stuck. Please could someone tell me how to show this? What I tried: My first attempt was to use ...
-3
votes
1answer
22 views

Let 'S' be the number of squares among the integers from 1 to 2013. let Q be the number of cubes among the same integers. [closed]

Let 'S' be the number of squares among the integers from 1 to 2013. let Q be the number of cubes among the same integers. then what will be the equation?
0
votes
0answers
14 views

How many bounded residues?

Given $a\in\Bbb N$, how many integers $\frac{a}2<b<a<c<2a$ are there such that $b^{-1}a\bmod a^2<(\log a)$, $c^{-1}a\bmod a^2<(\log a)$? Counting argument seems to imply there should ...
-1
votes
3answers
36 views

Prove $a|b \wedge b|a \implies a=\pm b$ [duplicate]

Let $a,b\in\mathbb{Z} \backslash \{0\}$. Show that $a\mid b$, $b\mid a$ $\implies a=\pm b$. I can see why this is true, but not write it down.
23
votes
2answers
835 views

A false conjecture by Goldbach

In 1752 Goldbach send this conjecture to Euler: "Every odd integer can be written in the form $p+2a^2$ where $p$ is a prime or $1$ and $a$ is a natural number (can be even 0)." This conjecture turned ...
1
vote
3answers
36 views

Expressing an Integer as the Sum of Two Powers of 4 in More than 1 way

Given the equation: $$ x^4 + y^4 = k, $$ where x, y and k are distinct non-zero integers, is there any k, such that there is more than one solution {x, y} for the above equation?
1
vote
1answer
40 views

solution of the equation $x^{22}\equiv{2}\pmod {23}$

$x^{22}\equiv{2}\pmod {23}$ does this have a solution? By Euler's formula since $23$ is a prime $x^{22}\equiv {1}\pmod {23}$ is true . But is this enough to dismiss the ...
1
vote
2answers
44 views

I need to prove: if $a|b$ and $a|c$ then $a|(bc)$?

what I did: $ak=b$, $aj=c$ so $bc= ak \times aj= a^2(kj)$. Let $m=bc$ and $n=kj$ Hence, $m= a^2n$ which is: $a^2|m = a^2|bc \leftarrow$ The proof must have been $a|bc$ ! Help?
2
votes
0answers
23 views

Application of Legendre, Jacobi and Kronecker Symbols

Legendre, Jacobi and Kronecker Symbols are powerful multiplicative functions in ...
1
vote
2answers
53 views

Maximum number of breakdowns for an $8$ digit number

Breakdown an $8$ digit number into successive digits such that each number is a prime and with increasing values to the right. For example, with $23353593$ we have: $2-3-3-5-3593$ $2-3-3-53-593$ ...
2
votes
0answers
36 views

Please help me understand Analytic Density $\lim_{\sigma \to 1^+}\frac{1}{\zeta(\sigma)}\sum_{n \in A} \frac{1}{n^{\sigma}}$

$d (A) = \lim_{\sigma \to 1^+}\frac{1}{\zeta(\sigma)}\sum_{n \in B} \frac{1}{n^{\sigma}}$ for $B \subset \Bbb{N}$. So clearly this limit is $0$ for reciprocally summable (convergent) $B$. My goal ...
3
votes
1answer
73 views

Irrationality of ${5^{1/7}}$

I am struggling with elementary proofs, and would appreciate any feedback as to the logic and structure of my work. Show that ${5^{1/7}}$ does not represent a rational number. Suppose ${5^{1/7}}$ is ...
1
vote
1answer
30 views

Find all $n$ such that $7$ divides $(2n+2)2^{n-1}$

For which $n$ the equation $(2n+2)\cdot 2^{n-1}\equiv 0\pmod{7}$ So I can look in this way? for which $k\in\mathbf{Z}$: $$ (2n+2)\cdot 2^{n-1}\equiv 7\cdot k \pmod{7}\,\,? $$
1
vote
2answers
29 views

A sequence of numbers prime to $4n$ with $n$ being odd

Let $n$ be odd. If I consider the sequence of $n$ numbers in the form $4k-1$ with $k$ running from $1$ to $n$ and take those with greatest common divisor with $4n$ being $1$ ( means those being prime ...
1
vote
2answers
19 views

Let $a$ have order $k$ modulo $n$. If $\gcd(h, k) = 1$, then show that $a^h$ also has order $k$

Here is my attempt but I am not able to proceed smoothly Since $\gcd(h, k) = 1$, we have $1=hx+ky$ for some integers $x,y$. $(a^h)^k = (a^k)^h \equiv 1\pmod{n}$ Lets suppose the order of $a^h$ is ...
0
votes
1answer
43 views

Show that $c\mid(ax+by)$

Freshman here. Let $a,b,c,x,y\in\mathbb{Z}$ and let $c\neq 0$. Assume $c\mid a$ and $c\mid b$. Show that $c\mid (ax+by)$. My approach Since $c\mid a$, $c\mid b$ and $x,y\in\mathbb{Z}$ then $c\mid ...
1
vote
1answer
51 views

Whether a real number is a dyadic rational iff its binary expansion terminates?

In self-studying a textbook on computability theory, I found that many of the exercises depend on the following factlet: A dyadic rational is a rational number whose denominator is a power of two, ...
4
votes
1answer
140 views

Prove that, if $p \in \mathbb{N}, p>5$, p prime

Prove this: Hypothesis Let $p \in \mathbb{N}, p>5$, p prime so that $p | (2^q + 3^q)$ where $q \in \mathbb{N}$, $q$ prime. Conclusion $p>q$ No idea how to start...
2
votes
4answers
109 views

Last two digits of $3^{7^{2016}}$

I need help with solving this Algebra problem: Find the last two digits of $3^{7^{2016}}$. Preferably using Euler's theorem.
1
vote
2answers
48 views

How to find $\#\{1\le x\le 5^k:5^k|(x^4-1)\}$?

Find $\#\{1\le x\le 5^k:5^k|(x^4-1)\}$. I am not so sure how it is done, nor am I completely sure if it is about any specific $k$ or all of them together. What I did arrive at, not being really sure, ...
2
votes
1answer
45 views

Prove that it is NOT true that for every integer $n$, 60 divides $n$ if and only if 6 divides $n$ and 10 divides $n$.

This is Velleman's exercise 3.4.26 (b): Prove that it is NOT true that for every integer $n$, 60 divides $n$ iff 6 divides $n$ and 10 divides $n$. I do understand that a number will be ...
2
votes
1answer
35 views

Ordered triples of n-powerful integers

Let’s say that an ordered triple of positive integers (a, b, c) is n-powerful if: $a \le b \le c$, $gcd(a, b, c) = 1$ and $a^n + b^n + c^n$ is divisible by $a + b + c$. For ...
2
votes
1answer
44 views

$\lim_{n\to\infty} \frac{n}{a_n} = \lim_{x\to\infty} \frac{1}{x}\sharp \{n \leq x: n \in A\}$ when the limit exists.

This question is about natural density $d(A) = \lim_{x\to\infty}\frac{1}{x}\sharp\{n \leq x: n \in A\}$. I'm trying to prove that when either that limit or this limit: $\lim_{n\to \infty} ...
1
vote
3answers
46 views

Show that $\gcd(m, n) = \gcd(n, r)$

Question: Let $m, n, q, r \in \mathbb Z$. If $m = qn + r$, show that $\gcd(m, n) = \gcd(n, r)$. Hence justify the Euclidean Algorithm. I found this question in a past test paper, but cannot ...
2
votes
1answer
75 views

X raised to power-X raised to power-3 equals to 3.

The question is what are the possible values of $x$ when we have $$x^{x^3} = 3$$ (that is $x^3$ in the exponent itself and not $x*3$). I solved one answer by guessing that $x = \sqrt[3]3$. My work ...
0
votes
2answers
26 views

Question regarding the Division Algorithm Proof

Division Algorithm: Let $a$ and $b$ be integers with $b>0$. Then there exists unique integers $q$ and $r$ such that $a = bq +r$ with $0 \le r < b$. I have a couple of questions ...
4
votes
2answers
59 views

Finding all solutions of $x^2+2x-15\equiv0 \pmod{105}$- Proof strategy.

Find all solutions of $x^2+2x-15\equiv0 \pmod{105}$. Now, I wanted to suggest a proof relying on the algorithm presented in class, and there are some parts where I could use some help or criticism. ...
1
vote
3answers
125 views

Why do we subtract [Combinatorics]

I asked Here This question and I am still confused. I got that, for at least one group together there are: $$3 \cdot 9 \cdot \binom{6}{3, 3}$$ But why do we subtract: $3 \cdot 9 \cdot 4$. Lets ...
4
votes
0answers
41 views

What's the order of growth of the 'double-and-rearrange' numbers?

This question asks about the reachability of some specific numbers via a procedure that starts from the number 1 and where a valid step is to either double the current number to yield a new number, or ...
9
votes
2answers
142 views

Can the identity $ab=\gcd(a,b)\text{lcm}(a,b)$ be recovered from this category?

Define the category $\mathcal{C}$ as follows. The objects are defined as $\text{Obj}(\mathcal{C})=\mathbb{Z}^+$, and a lone morphism $a\to b$ exists if and only if $a\mid b$. Otherwise ...
4
votes
1answer
82 views

Integer solutions to $x^2=2y^4+1$.

Find all integer solutions to $x^2=2y^4+1$. What I tried The only solutions I got are $(\pm 1 ,0)$, I rewrote the question as : is $a_{n}$ a perfect square for $n>0$ were $$a_0=0,\quad ...