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

learn more… | top users | synonyms (1)

3
votes
1answer
82 views

Elementary Twin Prime Attempt. [on hold]

There's a theorem somewhere that for sufficiently large $k$ there exists an infinite number of prime pairs with difference $2k$. Let $\ell$-prime pair mean a pair of primes separated by a distance of ...
2
votes
2answers
41 views

A property of every set of ten consecutive integers.

In the following example of ten consecutive integers we can see that $119$ and $121$ are each coprime with the others: $$114=2*3*19$$ $$115=5*23$$ $$116=2^2*29$$ $$117=3^2*13$$ $$118=2*59$$ ...
3
votes
1answer
38 views

Can two distinct sets of $N$ non-negative numbers have the same sum and sum of squares?

Suppose I have a set of $N$ non-negative numbers that sum to $A$. The sum of squares of these $N$ non-negative numbers sum to $B$. Here's the question: can there be a different set of $N$ ...
2
votes
3answers
43 views

Find last two digit

I have the following task: $1997^{1998} \pmod {100} = ?$ How to find it? Could you please, explain to me step by step with? Can you suggest any solution, without using Euler function? But rather, ...
0
votes
0answers
31 views

Does this set contain these numbers?

How would I go about proving whether or not every number $n=k^8$ is included in the set of all numbers $m=k^4$ ($n$ and $k$ are integers in both cases)?
5
votes
4answers
109 views

How many ways to write $2010$?

Let $ N$ be the number of ways to write $ 2010$ in the form $ 2010 = a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0$, where the $ a_i$'s are integers, and $ 0 \le a_i \le 99$. An example of ...
-1
votes
2answers
69 views

Proof that expression is integer, $\frac{(2n)!}{n!(n+1)!}$

can you help me with this excercises.. Proof that expression is integer, $$\frac{(2n)!}{n!(n+1)!}$$ I've tried for induction!! $p(1):\frac{(2)!}{2}=1 $ for $p(k)=\frac{(2k)!}{k!(k+1)!}$ for ...
2
votes
3answers
59 views

Proof that expression is integer, $\frac{(3n)!}{6^nn!}$

Can you help me with this exercises? Proof that expression is integer, $$\frac{(3n)!}{6^nn!}$$ I've tried for induction!! $p(1):\frac{(3)!}{6}=1 $ for $p(k)=\frac{(3k)!}{6^kk!}$ for ...
1
vote
1answer
9 views

Minimum of restricted linear combinations.

Let $\{N_0, ... , N_m\}$ be a set of natural numbers, then the minimum $(\geq 1)$ of all their linear combinations is their GCD. Is there a way to calculate that minimum if some $N$s can only be ...
6
votes
3answers
49 views

What phenomenon is this? $(2\Bbb{Z} + 1)\cup 3\Bbb{Z} = 2\Bbb{Z} \cup 3\Bbb{Z} + 3$

$(2\Bbb{Z} + 1)\cup 3\Bbb{Z} = 2\Bbb{Z} \cup 3\Bbb{Z} + 3$ Proof: $$ \begin{align*} 2\Bbb{Z} &= \bullet \circ \bullet \circ \bullet \circ \bullet \circ \dots \\ 3\Bbb{Z} &= \bullet \circ ...
2
votes
1answer
30 views

significance of Burton number theory exercise

Here is the question in Burton - I can solve it but am not sure what the importance of this exercise is and what Burton is trying to help me see with it: Find a prime divisor of the integer ...
4
votes
1answer
19 views

Properties of the Digit Product + Digit Sum of a number

The other day I started messing around with some properties and noticed a pattern emerging when the digit product and digit sum of a number were added together. For example, 15. (1+5)+(1*5) = 11. If ...
0
votes
1answer
10 views

For two periodic sets $A,B$, $A \cup (B + \{x\}) = \{y\} + A \cup B$ for some $y \in \Bbb{N}$.

Let $A,B$ be periodic subsets of $\Bbb{N}$, in other words each has an associated $T \in \Bbb{N}$ such that if $x \in A$, then $x + T \in A$, always, for instance. Let $x + A$ mean a translate of ...
0
votes
0answers
27 views

Moebius Identity

Is there alternative proof of Moebius identity i.e. sum of moebius function over divisor of n is zero than as suggested n page: ...
0
votes
0answers
13 views

Dirichlet product is associative

Is there alternative proof of fact: Dirichlet product on arithmetic function is associative than given in Dirichlet's product with number theoretic functions
1
vote
1answer
19 views

Every collection of periodic sets $A_n \subset \Bbb{N}$ (minus a common point), that avoids…

Let $\{A_n\}$ be a set of subsets of $\Bbb{N}$ each of which are periodic except for a common point. That is to say, there exists one and only one $x_0$, such that for each $n$, if $x \in A_n, x \neq ...
9
votes
4answers
139 views

Diophantine equation $(x+y)(x+y+1) - kxy = 0$

The following came up in my solution to this question, but buried in the comments, so maybe it's worth a question of its own. Consider the Diophantine equation $$ (x+y)(x+y+1) - kxy = 0$$ For $k=5$ ...
5
votes
1answer
37 views

Let $a$ and $m$ be positive integers such that gcd$(a,m)=1$. Show that: $a^m+1$ is not a prime.

Let $a$ and $m$ be positive integers such that gcd$(a,m)=1$. Show that: $a^m+1$ is not a prime. Though I didn't check the statement with so many integers, but it looks like the equation never ...
2
votes
1answer
37 views

How to prove the sum of squares larger than 1/n without induction? [duplicate]

known that: $1\geq R_1 \geq R_2 \geq \dots \geq R_n \geq 0$ and $\sum_{i=1}^n R_i=1$ To prove: $\sum_{i=1}^n R_i^2 \geq \frac{1}{n}$ Using induction, the problem can be easily proved. I'd like to ...
1
vote
2answers
31 views

Number 9 and age of mother when child is born.

If a mother's age is divisible by 9 when a child is born then once you go to the next decade,n every 11 years the child's age and mother's age are always the same two numbers in reverse order. For ...
0
votes
0answers
24 views

Prove that for every $k$ there exist fibonnaci number that ends with $k$ zeros.

Let $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n > 2$. Prove that for every $k$ there exist $F_m$ that ends with $k$ zeros. I tried using pigeonhole principle, but with no effect.
1
vote
2answers
65 views

“Proof” that $(2n)!$ is divisible by $2^n 5^{n-3}$ for $n\ge3$

Please explain, as clearly as possible, what is wrong with the following "proof" by induction that $\hspace{1.4 in}$$(2n)!$ is divisible by $2^n 5^{n-3}$ for $n\ge3$. (There clearly must be an ...
-5
votes
2answers
41 views

4th Grade Common Core question [on hold]

In the number $2,119$ if you move from the $1$ in the hundreds place to the $1$ in the tens place, what happens to the value of the $1$?
2
votes
0answers
19 views

Lehmer's totient problem generalization (adding a constant )

Lehmer's conjecture is an well-known open problem which states that the divisibility : $$\phi(n) \mid n-1$$ holds only for primes . This motivated me to ask the following : For which ...
6
votes
6answers
175 views

How is $\mathbb N$ actually defined?

I know perfectly well the Peano axioms, but if they were sufficient for defining $\mathbb N$, there would be no controversy whether $0$ is a member of $\mathbb N$ or not because $\mathbb N$ is ...
-2
votes
1answer
47 views

Solving problem of abstract algebra [on hold]

The question is that if $n$ is not a multiple of 23 then the remainder when $n^{11}$ is divided by 23 is 1 or -1(mod 23). Is it true or false? Please answer me.
3
votes
0answers
68 views

Solving an equation $x^{22}\equiv2 \bmod 23$ [on hold]

I have an abstract algebra problem which I am unable to solve. The problem is, if $x^{22}\equiv2 \bmod 23$, then $x$ has how many solutions? Please explain me.
2
votes
4answers
57 views

If $S$ is the set of all numbers of the form $3k + 1$, prove that any number $a$ in the set is prime or product of primes.

$S = \{1, 4, 7, 10, \ldots \}$ $10$ and $25$ are prime with regard to the elements of $S$ but $16 = 4 \times 4$ and $28 = 7 \times 4$ are not. I have been stuck on this problem as I am not sure of ...
0
votes
1answer
44 views

Maximum of $xy^3z^7$ in the plane $x+y+z=1$

A friend gave to me this problem and on having seen that I could not solve it in the first instance helped me with the hint of using the AM-GM inequality. PROBLEM.- To maximize the product $xy^3z^7$ ...
2
votes
0answers
38 views

Conjectured new primality test for Mersenne numbers

How to prove that this conjecture about a new primality test for Mersenne numbers is true ? Definition: Let $M_{q}=2^{q}-1 , S_{0} = 3^{2} + 1/3^{2} , \ and: \ S_{i+1} = S_{i}^{2}-2 \pmod{M_{q}}$ ...
1
vote
1answer
40 views

Is this a good generating function for Sum-of-divisors function?

I have an expression for the sum-of-divisors function defined as $$\sigma(n)=\sum_{d\mid n}d.$$ However I do not know how nontrivial or practical it actually is. Let us define ...
0
votes
1answer
21 views

Randomly picking 2 integers to compute a third one with equiprobability

I have a problem, that might be simple but I just don't see it for the moment. Supposing you have a finite set of integers $S_1$, I am looking for a simple function that when randomly picking two ...
0
votes
1answer
19 views

If $a, b \mid c \text { and } \gcd(a, b) = d, \text { then } ab \mid cd $

$a \mid c \to c = ak \text { and } b \mid c \to c = bj.$ $ak + bj = 2c = d \to c \mid d.$ $d \mid a \to a = dj.$ $c = ak = d(jk) \to d \mid c.$ So, $c = d.$ $a \mid c \text { and } b \mid c ...
0
votes
0answers
42 views

Is it true that this number is not prime?

Let $p=2^{4n}+1$. It follows that $p\equiv2,3,5 \mod{7}$. If $p$ is prime can we do better? I mean is it true that if $p\equiv 2 \mod{7}$ then $p$ is not prime? This is equivalent to prove that ...
4
votes
1answer
23 views

Basic question on equivalence relations.

Show that the following relation is an equivalence relation on the given set. $m \sim n$ in $\mathbb{Z}$ if $m \equiv n\,(\text{mod}\,6)$.
-4
votes
3answers
52 views

Prove or disprove divisibility claims? [on hold]

a) If $x^2$ is a multiple of $4$, then $x$ is a multiple of $4$ b) If $x^3$ is a multiple of $2$, then $x$ is a multiple of $2$
12
votes
3answers
924 views

Intermediate digits of 34!

Problem: Given that $34!=295232799cd96041408476186096435ab000000$. Find $a, b, c, d$. $a, b, c, d$ are single digits. I am able to find $a$ and $b$ but cant find $c, d$. I did the prime factorisation ...
5
votes
4answers
90 views

Proving $n! = n \Rightarrow (n = 1 \quad or \quad n = 2)$

I want to know whether my proof is correct. Any elegant proofs are welcome. $n\in\mathbb{N}.\quad$Prove $ (n!=n) \Rightarrow (n=1\quad or\quad n=2)$ $ (n!=n) \Rightarrow (n=1\quad or\quad n=2) ...
5
votes
2answers
49 views

Suppose $p, p+2, p+4$ are prime numbers. Prove that $p = 3$ not using division algorithm.

Suppose $p, p+2, p+4$ are prime numbers. Prove that $p = 3$ not using division algorithm. Hint: why can't $p = 5$ or 7? So I have done the two hints and in both cases I get a 9 in my set of numbers, ...
6
votes
2answers
67 views

Does every prime of the form $4k+1$ divide a number of the form $4^n+1$?

While playing around with Fermat's little theorem I was asking myself the question in the title and I can't answer it...
2
votes
0answers
18 views

How to pigeonhole the primes between $p_n$ and $p_{n+1}^2$ for twin prime conjecture?

For any full list of the primes up to the $n$th prime: $P = \{2, 3,5,\dots, p_n\}$, any natural number $q$ such that $ p_n \lt q \lt p_{n+1}^2$ that is not sieved by a prime in $P$ is also a prime. ...
2
votes
3answers
115 views

For each positive integer $a$, does there exist a positive integer $b$ such that $2b^2 + b \gt ab^2$?

The problem is this: Prove or give a counterexample to the following statement. For each positive integer $a$, there exists a positive integer $b$ such that $2b^2 + b \gt ab^2$. I've tried a couple ...
2
votes
4answers
67 views

Show that there is a number on the form $11 \dots 000 \dots 0$ divisible by 2014

Show that there is a number on the form $11 \dots 000 \dots 0$ (some number of $1$s followed by $0$s) divisible by $2014$. I'm helping someone practise for the math olympiad, and this question has me ...
-1
votes
1answer
38 views

Find the natural number $n>2$ such that $\frac{n!}{(n-1)!} + \frac{n!}{3!(n-3)!} = 2\frac{n!}{2!(n-2)!}$ [on hold]

I'm unsure how I'm supposed to solve the equation: $$\frac{n!}{(n-1)!} + \frac{n!}{3!(n-3)!} = 2\frac{n!}{2!(n-2)!} $$ given that $n>2.$
1
vote
3answers
82 views

How do you simplify $n!-(n-1)!$ [on hold]

I'm unsure how to simplify the expression $n!-(n-1)!$. Working as well as the final answer would be preferable.
11
votes
3answers
1k views

Can 720! be written as the difference of two positive integer powers of 3?

Does the equation: $$3^x-3^y=720!$$ have any positive integer solution?
3
votes
1answer
72 views

Prove that $s(n-1)s(n)s(n+1)$ is always an even number

Let $n$ be a natural number, and let $s(n)$ denote the sum of all positive divisors of $n$. Show that for any $n>1$ the product $s(n-1)s(n)s(n+1)$ is always an even number. I calculated the sum of ...
0
votes
1answer
21 views

Find a criterion for divisibility

Find a criterion such that $\displaystyle\sum_{i=1}^ni$ divides $\displaystyle\prod_{i=1}^ni^2$ for $n\in\mathbb N$. What I have done so far, $\displaystyle\sum_{i=1}^ni=\frac{n(n+1)}{2}$ and ...
0
votes
2answers
46 views

Weird question about natural numbers. Obvious or not?

Given any subset $A,C \subset \Bbb{N}$, there exists a maximal subset $B \subset \Bbb{N}$ such that for all $b \in B, a \in A, \ |b - a| \in C$. For instance $A = \{3,5\}$, $C = \{2,4\}$, then ...
4
votes
1answer
41 views

If $p$ is prime and $p\equiv 3 \pmod 5$, show that for every $a$, $x^5\equiv a \pmod p$ is solvable.

I tried all sort of things. I know it is supposed to be easy but I can't seem to be thinking anymore. I could really use even the most basic lead here. I tried working with primitive roots and ...