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

learn more… | top users | synonyms (1)

0
votes
3answers
45 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
67 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.
3
votes
1answer
211 views

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
55 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
41 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 [closed]

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
26 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
28 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
36 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
22 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
57 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)?$$
22
votes
13answers
751 views

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

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 ...
1
vote
2answers
66 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 ...
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
37 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
853 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
41 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
25 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
41 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
74 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
30 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
45 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
52 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
143 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
113 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
49 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
37 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
76 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
27 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
126 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
42 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
143 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
84 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 ...
2
votes
1answer
26 views

Prove or disprove: $ \sum_{b \vee d = x} \tau(b) \tau(d) = \tau(x)^3$

Can somebody prove or disprove? Let $\tau$ be the divisors function, so that $\tau(6) = \#\{ 1,2,3,6\} = 4$ $$ \sum_{b \vee d = x} \tau(b) \tau(d) = \tau(x)^3$$ Here I am using $b \vee d = ...
8
votes
1answer
134 views
+50

Determine all one to one functions $f:\mathbb{N}^* \rightarrow \mathbb{N}^*$ having the following property:

Determine all one to one functions $f:\mathbb{N}^* \rightarrow \mathbb{N}^*$ (where $\mathbb{N}^*$ means all positive integers) having the following property: For all $S$, where $S$ is a finite set ...
20
votes
5answers
3k views

Proving that all integers are even or odd [duplicate]

I know that $\mathbb{Z}$ is a group under addition with a multiplication defined. I have just the definition of even and odd integers: $n$ is even if $n = 2k$ for some integer $k$ and $n$ is odd if $n ...
3
votes
2answers
58 views

If $2xy$ divides $x^2+y^2-x$, prove that $x$ is a perfect square [duplicate]

This problem is from ( BMO Exam1991 ). I tried to solve but it was difficult. The problem is: If $ x^{2} + y^{2} - x $ is a multiple of $ 2xy $ where $x$ & $y$ are integers, prove that $x $ ...