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

learn more… | top users | synonyms (1)

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
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
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
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
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 ...
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 = ...
6
votes
0answers
74 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 $ ...
1
vote
0answers
62 views

Find the smallest number which leaves remainder 1, 2 and 3 when divided by 11, 51 and 91

While my preparation for exams, came across this question. "Find the smallest number which leaves remainder 1,2 and 3 when divided by 11,51 and 91" Find considerable time in solving this. I have ...
2
votes
2answers
148 views

2011 AIME Problem 12, probability round table

Nine delegates, three each from three different countries, randomly select chairs at a round table that seats nine people. Let the probability that each delegate sits next to at least one delegate ...
-1
votes
1answer
37 views

proving product of three consecutive numbers has a divisor $s^2 -1$

For all $N≥0$, if $N=k(k+1)(k+2), k>1$ is the product of three consecutive non-negative integers, prove that $N$ is divisible by some number $s^2 -1, s>k$. I was able to figure out that if we ...
4
votes
1answer
58 views

number of primes of the form |$n^2 - 6n + 5$|?

How can I find the number of primes of the form $|n^2 - 6n + 5|$ where $n$ is an integer? Through trial and error, I have found $n = 6$ (this one is obvious), and $2$. Are there any more, and what is ...
2
votes
2answers
62 views

percentage of integers such that $n^4 \pmod{16} \equiv 1$?

How do I find the percentage of numbers $n$ in the list $1^4, 2^4, ... 1000^4$ such that $n \pmod{16} \equiv 1$? I know that for any $x$, if $x \pmod{16} \equiv 1$, then $x^n \pmod{16} \equiv 1$, so I ...
10
votes
2answers
176 views

What would Gauss do in this case: adding $1+\frac12+\frac13+\frac14+ \dots +\frac1{100}$?

We all know the story related to Gauss that Gauss' class was asked to find the sum of the numbers from $1$ to $100$ as a "busy work" problem and and he came up with $5050$ in less than a minute. He ...
0
votes
0answers
45 views

Info on the locale of surjections from the Natural Numbers to the Real Numbers

On the nlab page for locales, it states that there is locale for the surjections from the Naturals to the Reals. This locale has no points (i.e. elements), since there are no such surjections, but the ...
0
votes
1answer
25 views

Testing for quadratic residues

Is $1487$ is a quadratic residue mod $2783$? I believe $1487$ is not a quadratic residue mod $2783$, and I'm thinking about using Legendre's symbol.
8
votes
2answers
184 views

Euler phi function and powers of two

For small values of n$\ge$1 it appears that one has the inequality $\phi(2^n)$ $\le$ $\phi(2^n + 1)$. However, it seems unlikely that this would hold for all n . Question: Are there any explicit ...
0
votes
0answers
41 views

For any arithmetic progression $n \in \Bbb{N} : n \equiv b \pmod a$, the natural density is $\frac{1}{a}$?

This question comes from here (page 10). Given that $d(A) := \lim_{x\to\infty}\frac{1}{x}\sharp\{n \leq x : n \in A\}$, how do I get that: 1) $d(n \equiv b \pmod a) = \lim_{x\to\infty}(\left [ ...
2
votes
0answers
30 views

A relation related with odd perfect numbers

It is easy to prove, using the relation $\prod_{d\mid n}d=n^{\sigma_0(n)/2}$ holds for $n\geq 1$ where $\sigma_0(n)$ is the number of divisors, the following Proposition. The integer $n\geq 1$ is ...
0
votes
0answers
29 views

How to prove $x^m = O(e^x)$ for any $m \gt 0$?

My attempt: It's true for $m = 1$ clearly. Now assume true for $m=1\dots M-1$. Then $x = O(e^x)$ and $x^{M-1} = O(e^{M-1})$. Lemma: if $f = O(g)$ and $f' = O(g')$ then $ff' = O(gg')$. Proof: $f = ...
-1
votes
4answers
56 views

Determine the greatest common divisor of two numbers

If $t$ is an odd positive integer I want to compute $(2t, 2t^2+t+2)$. What are if any the reduction steps or properties of the gcd that can help solve this?
1
vote
2answers
31 views

Simple question, what is meant by 'as $x \to \infty$ the number of squares $\leq x$ is $\sqrt{x} + O(1)$?

For $x \to \infty$: the number of squares $n^2 \leq x$ is $\sqrt{x} + O(1)$. From here (page 6). More specifically, do they mean that... I'm confused now. I'm really not sure what they mean ...
17
votes
1answer
212 views
+50

Integers $n$ for which the digit sum of $n$ exceeds the digit sum of $n^5$

This question is strongly inspired by The smallest integer whose digit sum is larger than that of its cube? by Bernardo Recamán Santos. The number $n=124499$ has digit sum $1+2+4+4+9+9=29$ while its ...
3
votes
2answers
50 views

Squares of a number yields a palindrome?

I was doing my statistics homework when I observed an interesting pattern: $ 11^2 = 121 $ $ 111^2 = 12321$ $ 1111^2 = 1234321 $ $ 11111^2 = 123454321 $ $ 111111^2 = 1.234565432 \times 10^{10} $ ...
4
votes
1answer
97 views

The smallest integer whose digit sum is larger than that of its cube?

79 is an example of a number whose digital sum is greater than that of its square (6241). Which is the least number, if any, whose digital sum is greater than that of its cube?
2
votes
2answers
78 views

Prove the root is less than $2^n$

A polynomial $f(x)$ of degree $n$ such that coefficient of $x^k$ is $a_k$. Another constructed polynomial $g(x)$ of degree $n$ is present such that the coefficeint of $x^k$ is $\frac{a_k}{2^k-1}$. ...
-1
votes
1answer
33 views

Combinatoric meaning of multinomial coefficients

$$\binom{n}{k}$$ means how many ways there are to choose $k$ objects from $n$ total objects. What is the combinatoric meaning of: $$\binom{n}{k_1, k_2, ... , k_n}$$ ??
1
vote
4answers
44 views

Looking for an example of a function which has (at least) two distinct left inverses

Looking for an example of a function which has (at least) two distinct left inverses I know that F has a left inverse if for $f: A \rightarrow B$ and $g: B \rightarrow A$ follows such that ...
3
votes
1answer
33 views

$\sum_{n \leq x} \frac{1}{n} = \int_{1}^x \frac{dt}{t} + O(1)$ help deriving it

On page 5 of: Probabilistic Number Theory by Dr.J¨orn Steuding, there's $\sum_{n=2}^{[x]} \frac{1}{n} \lt \int_{1}^{[x]} \frac{dt}{t} \lt \sum_{n=1}^{[x] - 1}$ Therefore integration yields: ...
1
vote
1answer
39 views

Distinguishability in Round Table Combinatorics

I have stumbled upon many questions, and one of the weaknesses is the ability to test if the concept is distinguishable or not. For example this: Nine delegates, three each from three different ...
-1
votes
0answers
33 views

Lifting quadratic residues

Let $p$ be an odd prime. Show that if $q$ is a quadratic residue modulo $p^x$ for some $x > 0$, then $q$ is a quadratic residue modulo $p^{x+1}$. We have $x^2=q \pmod {p^x}$, and $x^2-q=m ...
1
vote
2answers
50 views

$\liminf_{n\to\infty} \frac{\varphi(n)}{n} = 1$, not $0$

Let $\varphi(n) = \sharp\{1\leq x \leq n : (x,n) = 1\}$. Then $\liminf_{n\to\infty} \frac{\varphi(n)}{n} = 1$. My attempt: $\inf_{k\geq n}\frac{\varphi(k)}{k} \leq 1$ since for $n = 2$, this ...
8
votes
4answers
174 views

Is there a formulaic way to go from $\sum_{k=1}^{n} \frac{1}{k}$ back to $n$?

Say you want to sum $g(n) = \sum_{k=1}^{n} \frac{1}{k} = L$. Is there a simple formula to go from $L$ and deduce $n$? My attempt: For $n = 1$, the formula is $L$. Assume there is a formula for all ...
-2
votes
2answers
46 views

Integers modulo 4 and the parity of a particular equation. [closed]

If $s$ is a positive integer greater or equal to two I write \begin{equation} \phi_{2}(s) = \frac{s^{2}+s+4}{2} \end{equation} I want to show that \begin{equation} s =\begin{cases} \text{0 or 3 ...
-2
votes
1answer
152 views

Determining if two numbers are relatively prime. [closed]

What is the right direction here? I would like to prove the following or show that it is not true by a counter example. If $s \geq 2$ and $4 \not\mid s$ I write \begin{equation} \phi_{2}(s) = ...
4
votes
1answer
145 views

conjectured new generating function of fibonacci numbers

I conjecture a new generating function for the fibonacci numbers $F_{n}$. Given, ...
1
vote
2answers
35 views

Using L.C.M or H.C.F to determine the time at which two events occur simultaneously again

In an experiment, there are two light bulbs; one is red and one is green. The red light bulb flashes every 20 minutes an the green light bulb flashes every 25 minutes. If the two light bulbs flash at ...
1
vote
0answers
26 views

Is it possible that some combination of partial sums of $\sum \sqrt{k}$ be a rational number? $\text{where } k \text { not a perfect square}$

Is it possible that some combination of partial sums of $\sum \sqrt{k}$ be a rational number? $k=2,3,5,\cdots \text{where } k \text { not a perfect square}$ More ever : can a linear combination of ...
1
vote
0answers
23 views

Generating function for writing an even number as a sum of at most k squares

I would like to find the exact number of ways in which $n$ can be represented as a sum of at most $k$ squares such that each term is less than or equal to say, $N$. A generating function for this ...
0
votes
2answers
39 views

Confusion in notations of number theory

In several materials I saw the notation for complete residue system as follows $\mathbb{Z}_n=\{0,1,2,3,\cdots, n-1\}$ But in some other materials/ in the same material, It says that the above ...
4
votes
3answers
483 views

Probability of a natural number being divisible by 2, 3, or 5?

I'm trying to calculate the probability of a natural number being divisible by 2, 3, or 5 and I feel as if I may have found the answer. But I wanted to see if anyone sees anything wrong with my ...
1
vote
5answers
49 views

Help with proof that $\sum_{n \in \Bbb{N}} \frac{1}{an + b}$ also diverges?

We know that $\sum_{n \in \Bbb{N}} \frac{1}{n}$ diverges. So it seems likely that $\sum_{n \in \Bbb{N}} \frac{1}{a n + b}$ will for any real $a, b$. I'm having trouble proving it just for the ...
4
votes
3answers
285 views

Find all integers such that $2 < x < 2014$ and $2015|(x^2-x)$

Find all integers, $x$, such that $2 < x < 2014$ and $2015|(x^2-x)$. I factored it and now I know that $x > 45$ and I have found one solution so far: $(156)(155)= (2015)(12)$. It's just that ...