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

learn more… | top users | synonyms (1)

3
votes
1answer
129 views

Is this proof that $\lfloor x \rfloor \geq n \left\lfloor \frac{x}{n} \right\rfloor$ correct?

In this text the fractional part of a real $x$ shall be denoted $\{x\}$, such that $x = \lfloor x \rfloor + \{x\}$. Theorem: $$ \forall x \in \mathbb{R}_{\geq 0} \forall n \in \mathbb{N}_{\geq 1} : ...
1
vote
1answer
70 views

Can $2a^2+2a+2ab^2+b^2$ be written algebraically as the sum of three triangular numbers?

Let $T(n)=\tfrac{1}{2}n(n+1)$ denote the $n$th triangular number. I'm looking for an identity of the form $$ 2a^2+2a+2ab^2+b^2 = T(f(a,b)) + T(g(a,b)) + T(h(a,b))\tag{$\star$} $$ where $a,b$ are ...
0
votes
1answer
93 views

Prove with combinatorial arguments this equation [duplicate]

Prove with combinatorial arguments, that, $\forall n \in \mathbb{N}$. $$\sum_{k=0}^n (-1)^k {n \choose k} =0$$
-1
votes
2answers
89 views

Prove that $6! \mid n(n+1)…(n+5)$ [closed]

Prove that for all $n \in \mathbb{Z}$, $6! \mid n\cdot(n+1)\cdots(n+5)$ using only criteria of divisibility (without using combinatorial arguments).
0
votes
1answer
64 views

Greatest integer function inequality

I am trying to show that $[x+y] \geq [x] + [y]$, where $x,y \in \Bbb {R}$. This is my work so far: Assume $x,y \in \Bbb {R}$. Suppose $[x]=m$ and $[y]=n$. Then $m,n \in \Bbb {Z}$. So then $m \leq ...
1
vote
1answer
58 views

If p|a^2 then P^2|a^2. Show that it is true or false.

For natural numbers $a$ and $p$ with $p$ prime, if $p$ divides $a^{2}$ then $p^{2}$ also divides $a^{2}$. My understanding to the is if $p\mid a$, then $gcd(a,p)$ should not be equal to 1 and so as ...
0
votes
1answer
24 views

How to show that

If $f$ is a multiplicative function proof that: i) $f^{-1}(p^{2})= [f(p)]^{2}-f(p^{2})$ ii) $f$ is completely multiplicative $\Longleftrightarrow f^{-1}(p^{\alpha}) = 0; \forall p $ prime $\alpha ...
0
votes
0answers
85 views

Using jugs filled with water problem

Given jugs $m$ and $n$ liters (WLOG $m<n$) is it always possible to get all $i$, $0 \leq i \leq n ?$ If so, prove it. If not, explain which $i$ you can get. Is there also a minimum number ...
0
votes
0answers
38 views

Prove for all whole numbers n, $(n+1)(n+2)…(2n-1)(2n)=2^n(1)(3)(5)…(2n-1)$ [duplicate]

Prove for all whole numbers n, $(n+1)(n+2)...(2n-1)(2n)=2^n(1)(3)(5)...(2n-1)$. I got upto $(2n)(2n-2)(2n-4)...=2^n$, after which I'm stuck.
0
votes
2answers
146 views

What does “finding an element” in $\mathbb Z_n$ mean?

I am currently in my last year of high-school and I try to learn Algebra on my own, one of my textbook exercise ask me to Find elements: $$ ...
0
votes
1answer
121 views

Greatest integer function question

I'm trying to show that, if $x \leq y$, then $[x] \leq [y]$, where $x,y \in \Bbb {R}$. I figured out that $[x] \leq x \leq y$, which would imply that $[x] \leq y$. I think that I need to now show ...
1
vote
1answer
93 views

Question on Eisenstein Primes

I understand that this is the characterization of an Eisenstein Prime: "An Eisenstein integer $z = a + bω$ is an Eisenstein prime if and only if either of the following (mutually exclusive) ...
1
vote
2answers
92 views

Metric on natural numbers united with infinity

can anyone give me an example for the following metric $d$? Let $\Omega = \mathbb{N}_+ \cup \{ \infty \}$ and $d$ be a metric such that all points $n \in \mathbb{N}_+$ are isolated w.r.t. $d$ and ...
0
votes
2answers
47 views

What is the value of the sum of two greatest integers

What is the value of $[x]+[-x]$, where $x \in \Bbb {R}$? Definition: $[x] \leq x < [x]+1, x \in \Bbb {R}$ I think I figured out that the value will be either 0 or -1 for all $x \in \Bbb {R}$ For ...
3
votes
2answers
134 views

The remainder of $1^1+2^2+3^3+\dots+98^{98}$ mod $4$

How can I solve this problem: If the sum $S=(1^1+2^2+3^3+4^4+5^5+6^6...+98^{98})$ is divided by $4$ then what is the remainder? I know that all the even terms I can ignore since ...
2
votes
3answers
101 views

How do I prove that numbers not divisible by 3 can be represented as 3x+1 or 3x-1?

I saw that some proofs used the fact that numbers not divisible by $3$ can be represented as $3x+1$ or $3x-1$. But how do I prove that it is true?
1
vote
1answer
60 views

How to show that $f(p^{k}) = f(p) \cdot f(p^{k-1}) \Longrightarrow f(p^{k}) = [f(p)]^{k}$ [closed]

If f is an arithmetic function such that $f (1) = 1$ and $p$ is a prime number. Prove that: $\forall k \in \mathbb{N}$ $f(p^{k}) = f(p) \cdot f(p^{k-1}) \Longrightarrow f(p^{k}) = [f(p)]^{k}$
-2
votes
2answers
71 views

How to show that $ \sum_{d/n} \mu^{2}(d)/\phi(d) = n/\phi(n)$? [closed]

$\forall n, n\in\mathbb{N}$ $\frac{n}{\phi{(n)}} = \sum_{d/n} \frac{\mu^{2}(d)}{\phi(d)}$ Where $\mu$ is the Möbius function.
-2
votes
1answer
28 views

Is there a notation for incomplete quotient

If $n, m > 0$ are integers and $m \nmid n,$ how to denote the incomplete quotient this division?
0
votes
1answer
45 views

Prove Inequality Is True By Induction

$3^n ≥ n^3 +1$ for the integer $n ≥ 4$. I let $n=0$ and the inequality is turns into $1 ≥ 1$ which is true. Then I let $n=n+1$ and the inequality turns into $3^{n+1} ≥ (n+1)^3 +1$. Now from here I ...
0
votes
2answers
40 views

Factorial Summation Problem [duplicate]

$$\sum_{j=0}^n j\cdot j!$$ I got $(n+1)!-1$ as the answer but I'm not sure if that's right or how I even got to that answer exactly. (my paper is a mess of random work and I can't make it out). Can ...
0
votes
1answer
50 views

If $n$ is a composite number, then $(7^n-1)/6$ is also composite

Let $n \ge 2$ and $a_n = \dfrac{7^n−1}{6}$. Prove that if $n$ is composite then $a_n$ is composite. I would normally prove something like this with induction but in this case I don't know how to ...
1
vote
0answers
38 views

Why is multiplication commutative - intuitive explanation [duplicate]

While I know that both addition and multiplication are commutative operations, I can easily visualize that, e.g. 3 + 4 = 4 + 3 = 7 by thinking of seven objects in a row and separating them into two ...
1
vote
2answers
142 views

Does the equality $1+2+3+… = -\frac{1}{12}$ lead to a contradiction? [duplicate]

Is $1+2+3+4+5.... = -\frac{1}{12}$ self-contradictory ? I've heared much that $1+2+3+.... = -\frac{1}{12}$, although the fact that this series is diverging. I saw a proof of it by a physicist. In ...
11
votes
5answers
1k views

What is the meaning of set-theoretic notation {}=0 and {{}}=1?

I'm told by very intelligent set-theorists that 0={} and 1={{}}. First and foremost I'm not saying that this is false, I'm just a pretty dumb and stupid fellow who can't handle this concept in his ...
0
votes
1answer
54 views

GCD's and Relatively Prime numbers

Prove that $gcd(a,bc)=1$ iff both $gcd(a,b)=1$ and $gcd(a,c)=1$. I know I need to prove it both ways but is this how you do it? Proof: Assume that $gcd(a,bc)=1$. So $a$ and $bc$ are relatively prime ...
0
votes
2answers
99 views

Greatest Common Denominator and linear combination

I know the gcd of 616 and 427 is 7, but I know need to do a linear combination of it. So there exists $x, y$ such that $$7=616x+427y$$ How do I solve for x and y?
1
vote
1answer
53 views

Is there a composite integer $n \geq 9$ such that $n \nmid (n-1)!$? [duplicate]

Is there a composite integer $n \geq 9$ such that $n \nmid (n-1)!$? If we are not talking about composites then by Wilson's theorem we have $n \nmid (n-1)!$.
1
vote
1answer
60 views

Ternary Expansion of $1/4$

I know that the ternary expansion of $1/4$ is $0.020202\cdots$. The verification is easy: $0.020202\cdots$ is nothing but the infinite series $2/3^2+2/3^4+2/3^6+\cdots $ which converges to $1/4$. ...
1
vote
1answer
355 views

Any number $n>11$ is a sum of two composite numbers

I have seen the following problem: Any number $n>11$ can be formed by the sum of two composite numbers and it says to prove it by contradiction. I have done the following: Assume that the sum ...
0
votes
4answers
77 views

prove that for every integer,$ n$, greater than $1$,$ (3^{2n+1}) + (5^{2n-1})$ is divisible by $16$

Could someone please help me out with this proof? Prove that for every integer $n≥1$, $3^{2n+1} + 5^{2n-1}$, is divisible by $16$. I get to a point where I have... $$3^{2k+1} \cdot 3^2 + 5^{2k-1} ...
1
vote
0answers
49 views

Could you give a definition of what is a superior highly composite number using only words?

I know very well what is a superior highly composite number, but I would like to see how could we (roughly) define what is a superior highly composite number using only words (using no equations and ...
1
vote
0answers
189 views

Any Computational Number Theory Book, include software programs for key steps of the proofs of major theorem?

All: Can anyone recommend some Computational Number Theory Books, which include software programs for key steps of the proofs of major theorem ? Some computational number theory books only include ...
8
votes
1answer
297 views

Seeking help extending Vieta-jumping to higher powers

I am trying to prove the following conjecture. Conjecture. If $r > s \ge 1$ are relatively prime integers such that \begin{equation} (r-s)^4-1 \equiv 0\!\pmod{4r^2s}, \tag{1} \end{equation} ...
1
vote
1answer
127 views

lebesgue's identity

In the Lebesgue's identity $$ a^2+b^2+c^2=d^2$$ where: $$a=m^2+n^2-p^2-q^2$$ $$b=2(mp+nq) $$ $$c=2(mq-np) $$ $$d=m^2+n^2+p^2+q^2 $$how can we write $(m,n,p,q)$ as a function of the integers ...
-1
votes
2answers
214 views

Sum of squares of any three consecutive even integers.

There is this question and my solution. But I am not sure whether there is anything to add to my solution. What conclusions can you draw about the sum of the squares of any three consecutive even ...
1
vote
1answer
125 views

Let $p \geq 2$. Prove that if $2^p-1$ is prime then $p$ must also be prime.

Would the following be a valid proof? Let $r$ and $s$ be positive integers, then the polynomial $x^{rs}-1=(x^r -1)(x^{s(r-1)}+x^{s(r-2)}+\cdots+x^r+1)$. So if $p$ is composite (say $rs$ with ...
3
votes
5answers
1k views

Show that lcm$(a,b)= ab$ if and only if gcd$(a,b)=1$

Not sure how to begin. If gcd$(a,b)=1$ what can I deduce from that?
2
votes
1answer
38 views

discrete mathematics - if then proof

show that for integers x and y, $$x^2 + y^2 = 0$$ x = 0 and y = 0 My approach was: suppose x ≠ 0 and y ≠ 0 and $x^2 + y^2 = 0 $ $x^2 = -(y^2)$ Then, LHS is always positive but RHS is always ...
2
votes
1answer
94 views

A question about how to express a fraction as ${1\over q_1}+{1\over q_2}+ \cdots+{1\over q_N}$

Let $x$ be a positive rational number, strictly between $0$ and $1$. Prove that there is a finite strictly increasing list of positive integers $2 \leq q_1<q_2<\cdots<q_N $ such that ...
2
votes
3answers
122 views

Factorial as a sum. Insight appreciated

I recently posted an answer to a question about ways to express the factorial function as a sum. I posted the following formula, which I discovered several years ago and I haven't seen anywhere else: ...
0
votes
2answers
64 views

Determine the number of digits in $4^n$

Let $n$ be a natural number. How can we determine the number of digits in $4^n$? For example $4^{20}$ has $13$ digits.
1
vote
6answers
125 views

The diophantine equation $a^2+ab-b^2=0$

I first tried with brute force with $-1000 \leq a,b \leq 1000$ but found no solution. But then a simple argument showed me that there was no solution. Not only in the integers, but even for the ...
2
votes
2answers
42 views

Does $x\equiv ay \pmod{p^{2m}}$ always have non-trivial solutions $x,y$ with $\lvert x \rvert,\lvert y \rvert \leq p^m$?

Given a positive integer $m$, a prime $p$ and an integer $a$, I would like to prove that $$ x \equiv ay \pmod{p^{2m}} \qquad \lvert x \rvert,\lvert y \rvert \leq p^m $$ always has at least one ...
2
votes
2answers
93 views

Is there a ring $R \neq \mathbb{Z}$ such that the fundamental theorem of arithmetic holds in $R$?

Is there a ring, unequal to $\mathbb{Z}$, for which the fundamental theorem of arithmetic holds? Please also give an example if an existential proof is given.
1
vote
2answers
102 views

Solve $a^2+b^n=c^2$

Let $a,b,c$ be co-prime integers >1, for all $n>2$, I need help finding the integral solutions of the diophantine equation $a^2+b^n=c^2$. I saw the result but I am curious about to how to get ...
2
votes
1answer
39 views

generalization of chinese remainder

Let $n_1$, $n_2$,...$n_k \in N^{+}$ and $c_1,c_2,..c_k \in Z$. Then the system of linear congurences $x\equiv c_i\pmod {n_i}$ for $i=1,2,..k$ has a solution if and only if $\gcd(n_i,n_j)\mid ...
2
votes
2answers
57 views

Prove that there are no integers with order $4$ in modulo $12$

Prove that there are no integers with order $4$ in modulo $12$ This is given as an obvious fact without any proof in my textbook. However I am not able to see why there cannot be any integer ...
1
vote
5answers
129 views

If $p^2\,$is divisible by 3, why is p also divisible by 3? [duplicate]

I came across this in proving that the $\sqrt{3}$ is irrational
0
votes
0answers
70 views

Robin's Inequality

Accoriding to this publication: On Robin’s criterion for the Riemann hypothesis. YoungJu CHOIE, Nicolas LICHIARDOPOL, Pieter MOREE, Patrick SOL On page 2 it states that 2 and 1 fails Robin's ...