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

learn more… | top users | synonyms

0
votes
1answer
27 views

Product of greatest integer functions

I am trying to show that if $x >0$ and $y > 0$ and $x,y \in \Bbb {R}$, then $[x][y] \leq [xy]$. This is my work so far: Assume that $x,y \in \Bbb {R}$ and $x,y >0$. Now suppose that ...
2
votes
1answer
16 views

Assume that the order of $a$ in $ \pmod n$ is $h$ and the order of $b$ in $ \pmod n$ is $k$. Show that the order of $ab$ in $ \mod n$ divides $hk$

Assume that the order of $a$ in $ \pmod n$ is $h$ and the order of $b$ in $ \pmod n$ is $k$. Show that the order of $ab$ in $ \mod n$ divides $hk$ $ a^h \equiv 1 \pmod n $ $ b^k \equiv 1 \pmod n ...
3
votes
1answer
35 views

Find the order of $2$ in $\mod 2^{n} -1 $

Find the order of $2$ in $\mod 2^n-1$ I know that the order of $2$ in $\mod 2^n-1$ is the smallest positive integer $k$ such that $$2^k \equiv 1 \pmod {2^n-1}$$ How to proceed from here ? Any ...
0
votes
0answers
67 views

How does $\sum\limits_{i=1}^n i^c \lfloor{n/i}\rfloor$ converge?

How to converge such series : $$y = \sum\limits_{i=1}^n i^c \lfloor{n/i}\rfloor$$ where c can be any constant value, and particularly $i^c = f(i).~$ Also, $f(x)$ is not a Euler's totient function.
2
votes
2answers
146 views

A question on gcd :

Here's the question: Let $a$ and $b$ be integers such that $\gcd(a,b) = 1$. Let $r$ and $s$ be integers such that $$ar + bs =1.$$ Prove that $\gcd(a,s) = \gcd(r,b) = \gcd(r,s) = 1$. I was stuck ...
0
votes
0answers
24 views

Similar to Bernoulli sequence

The sequence of Bernoulli numbers $(B_m)_{m\ge 0}$ can be defined by $B_0=1$, $B_1=-1/2$ and $\sum_{i=0}^{n-1}{\binom{n}{i}B_i}=0$ whenever $n\ge 2$. This is in turn equivalent to ...
3
votes
1answer
68 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} : ...
2
votes
1answer
58 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
2answers
79 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
0answers
17 views

Find the Number of $k$ Satisfying the Condition

Determine the number of integers $k$ such that $\left \{\dfrac{kq}{p}\right\}<\left \{\dfrac{k(q-1)}{(p-1)}\right\}$ where $1 \leq k \leq \dfrac{p-1}{2}$ and $p$ , $q$ are both odd primes with ...
0
votes
1answer
17 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 ...
0
votes
0answers
20 views

Uniqueness of the form of consecutive composite integers

If we are asked to give a given number $n$ of consecutive composite integers, then we probably would give the integers of the form $$(n+1)! + m$$ where $2 \leq m \leq n+1$ is an integer. However, ...
-3
votes
2answers
40 views

How to show that [closed]

If $f$ is a function $f: \mathbb{N}\longrightarrow\mathbb{N}$ that verify the conditions $\forall m,n \in \mathbb{N}:$ i) $f(m+n) = f(m) +f(n) -1$ ii) $f(2n+1) = f(n) + 2(n+1)$ Find $f(2014)$
1
vote
1answer
53 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
22 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
37 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
35 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
73 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
2answers
47 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
31 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) ...
0
votes
2answers
42 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 ...
1
vote
2answers
80 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
45 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
53 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
47 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
22 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
27 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
22 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
41 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 ...
0
votes
2answers
91 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 ...
0
votes
1answer
40 views

Asymptotic sum of the squares of the first n primes [closed]

I know there is an asymptotic formula for the sum of the squares of the first n primes, but I have been unable to find it.
0
votes
1answer
30 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
53 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
42 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
24 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$. ...
0
votes
4answers
55 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} ...
0
votes
0answers
18 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
72 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 ...
0
votes
0answers
30 views

Euclidean division

I'm implementing a big integer package and I have division working correctly on unsigned numbers but I need to implement Euclidean division, i.e. for negative inputs the remainder needs to be always ...
6
votes
0answers
107 views
+50

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} ...
-2
votes
0answers
27 views

Find all possible positive integral solution to following equation? [duplicate]

Please help me finding all possible positive integral solutions to following equation: $$2(x_1+x_2+_3+x_4+x_5+x_6) + x_7 = n$$ where $$0 < x_1,x_2,x_3,x_4,x_5,x_6,x_7$$ $$1 < N $$ $N$ is ...
0
votes
0answers
23 views

Polynomial divisibility question

Let $f_n(a)$ be a polynomial of degree $n+1$ with integer coefficients, such that $f_n(a) > 0$ when $a > 0$. If there exists an integer $m > 1$ such that $$m^{n-1} \mid \gcd(f_n(m-1),\ ...
0
votes
0answers
44 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 ...
0
votes
0answers
12 views

Any work on the alternating sign version of the Dirichlet Divisor Problem?

Suppose I have functions $$\displaystyle E_1(k) = \sum_{j=1}^n (-1)^{j+1}$$ $$\displaystyle E_2(k) = \sum_{j=1}^n \sum_{k=1}^{\lfloor \frac{n}{j} \rfloor} (-1)^{j+1}(-1)^{k+1}$$ $$\displaystyle ...
-1
votes
2answers
53 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
102 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 ...
2
votes
5answers
78 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
30 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 ...
1
vote
2answers
39 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
54 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.