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

learn more… | top users | synonyms (1)

0
votes
1answer
35 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
29 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
0answers
31 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
18 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
38 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
20 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
45 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$
10
votes
3answers
884 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
87 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) ...
4
votes
2answers
47 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
65 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
17 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
110 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
63 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
70 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
20 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
45 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
37 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 ...
0
votes
1answer
22 views

Does there exist a finite set of homogeneous polynomials (+ property) whose unique solution is equivalent to a finite sequence of naturals?

Consider the set $\{2,3,5\}$ of natural numbers. Letting $p = 2, q = 3, r = 5$ we have: the polynomial equations: $$p + q = r, \\ p^2 + r = q^2 \\ q^3 - p = r^2 $$ Each is a homogeneous ...
5
votes
2answers
67 views

In the $x + 1$ problem, does every positive integer $x$ eventually reach $1$?

I know that the more famous $3x + 1$ problem is still unresolved. But it seems to me like the similar $x + 1$ problem, with the function $$f(x) = \begin{cases} x/2 & \text{if } x \equiv 0 ...
0
votes
1answer
31 views

Lower bound for $\Pi(n)$ - viability of probabilistic theory

Can somebody check the validity of my arguments below, and tell me why its wrong or right? Consider the sequence of non-negative integers. Let $a_0=0, a_1=1, ..., a_i=i,...$ Divisiblilty of $a_i$ ...
1
vote
1answer
33 views

Find all primes $p$ for which $x^2+2x+4\equiv 0 \pmod p$ is solvable. Am I correct?

Getting ready for an exam, I would like to focus on the correctness of my solution, final results and assumptions, and would appreciate any comment regarding it or even additional ...
0
votes
0answers
18 views

The distribution of prime and semi-prime.

Let $\alpha$ be an integer and $\rho_1,\rho_2$ some prime such that $\alpha=\rho_1\cdot\rho_2+1$, and $\beta$ the number of all semi-prime less than or equal to $\alpha$. Prove ...
1
vote
2answers
28 views

Proving that $a^{b}$ is rational (Elementary number theorey) [duplicate]

Prove that there exist irrational numbers $a$ and $b$ such that $a^{b}$ is rational. What i tried Prove by contradiction I assume the statement For all rational numbers $a$ and $b$ such that ...
0
votes
0answers
28 views

Showing $pk+1|p^p-1$ implies that $k$ is even

Suppose $p$ is an odd prime such that $pk+1$ divides $p^p-1$. Prove that it is not possible for $k$ to be odd. Here's my solution: Assume to the contrary that $pk+1$ does divide $p^p-1$ We can ...
2
votes
0answers
29 views

$a$ and $n$ are relatively prime then there exists an integer $k$ such that $ak \equiv 1(\mod n) $.

Let $n \in Z$, $n > 1$ and let $a \in Z$ with $1 \leq a \leq n$. Prove that if $a$ and $n$ are relatively prime then there exists an integer $k$ such that $ak \equiv 1(\mod n) $. Proof: Suppose ...
1
vote
1answer
25 views

Dirichlet theorem

Can anyone give a simple number theory proof for the Dirichlet theorem? Statement of Dirichlet theorem:given any two numbers a and b whose g.c.d is 1,Prove that infinitely many primes exist in the ...
3
votes
2answers
63 views

Prove that for every natural number $n > 2$ there is a prime number between $n$ and $n!$

So I have already read this page with the solution: For all $n>2$ there exists a prime number between $n$ and $ n!$ Now I was able to reason that $p < n!$ Because I was given the hint that ...
3
votes
2answers
112 views

Perfect numbers

Define a Perfect (capital-P) number as a natural number that is equal to the sum of its Divisors excluding 1 and the number itself. (So the Divisors of 28 are 2, 4, 7, 14, summing to 27.) Is there any ...
2
votes
1answer
95 views

Difficult sets of Equations, counting

Let $ m$ be the number of solutions in positive integers to the equation $ 4x+3y+2z=2009$, and let $ n$ be the number of solutions in positive integers to the equation $ 4x+3y+2z=2000$. Find the ...
0
votes
0answers
23 views

Is this an Alternate proof of the Uniqueness of Remainder Th.?

$\mathbf{Theorem}: \forall$ pairs of integers $(a,b)$, $\exists$ unique integers $q, r$ such that $a=bq+r$ and $0\le r \lt |b|$ Assuming that the existence of the integers $q,r$ is already proven, ...
0
votes
1answer
29 views

If $n=x^2+3y^2$ then any prime in $n$'s factorization is of an even power.

If $n=x^2+3y^2$ then any prime $p$ such that $p\equiv 2 \pmod 3$ in $n$'s factorization is of an even power. I have been spending hours trying to solve this because of some some issues withholding any ...
5
votes
1answer
54 views

Missing values of the ratio $\frac{(x+y+z)^2}{x^2+y^2+z^2}$

Let $x,y,z$ be some positive integers. Is it true that we cannot find any positive integer $n$ for which $$ \frac{(x+y+z)^2}{x^2+y^2+z^2}=1+\frac{2}{3n}\,\,? $$
2
votes
0answers
21 views

Smallest number of workers in factory, Diophantine approximation

Q. In a factory, the percentage of male workers was $53.7802\%$ (rounding to nearest fourth decimal place) last year. What is the smallest number of female workers working there? Hint: Diophantine ...
2
votes
1answer
33 views

$(a^{2^n}+1,a^{2^m}+1)=1 or 2$ [duplicate]

Prove that if $m\not =n,a$ are positive integers then $(a^{2^n}+1,a^{2^m}+1)$ is $1$ if $a$ is even and $2$ if $a$ is odd. I solve the problem in the following way: I assume that $m>n$ then ...
4
votes
1answer
55 views

Is every sufficiently large even integer the sum of distinct primes?

Is every sufficiently large even integer the sum of (any number of) distinct primes? No doubt this question has been asked before; does the conjecture/theorem have a name? It is related to ...
1
vote
1answer
66 views

Integer solutions to $ab=a+b$

If $ab=a+b$ is there only one possible solution,i.e. $a=b=2$? ($a$ and $b$ not equal to zero and are integers). If not what are the others? I have proved that $a$ always needs to be equal to $b$. My ...
5
votes
0answers
44 views

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have?

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have? options given: (a) either $1$ or $2$ (b)$1$ or $3$ (c)either $2$ or ...
3
votes
2answers
513 views

A number n is not a Prime no and lies between 1 to 301,how many such numbers are there which is not divisible by 2,3,5,7.

A number n is not a prime and lies between $1$ and $301$, how many such numbers are there which are not divisible by $2$, $3$, $5$, $7$? a) $6$ b) $8$ c) $10$ d) $12$ My approach: ...
2
votes
2answers
85 views

If $\gcd(ab,c)=d$ and $c|ab$ then $c=d$

For all positive integers $a$, $b$, $c$ and $d$, if $\gcd(ab, c) = d$ and $c | ab$, then $c = d$. Need help proving this question, I know that $abx + cy = d$ for integers $x,y$ and that $c|ab$ can be ...
0
votes
1answer
51 views

Property for the natural numbers.

This question is inspired by another question I had, where I wanted to prove something about the natural numbers. Often in analysis books I see some proofs, where they use the natural numbers, but it ...
0
votes
1answer
17 views

$f_n(x) = \left\lfloor \frac{\sin(2\pi (x / n + 1/ 4) + 1 }{2}\right\rfloor$ and related

$f_n(x) = \left\lfloor \frac{ \sin(2\pi (\frac{x}{n} + \frac{1}{4})) + 1}{2}\right \rfloor = 1 \iff x = kn$ and $ f_n(x) = 0 \iff x \neq kn$. Let $g_n(x)$ be what's within the floor brackets. Then ...
0
votes
2answers
77 views

How many pairs $(m, n)$ exist?

For certain pairs $ (m,n)$ of positive integers with $ m\ge n$ there are exactly $ 50$ distinct positive integers $ k$ such that $ |\log m - \log k| < \log n$. Find the sum of all possible ...
1
vote
1answer
35 views

For every natural integer $N>3$ there are at least two distinct prime numbers $p$ and $q$ such that $\dfrac{p+q}{2}=N$ and $N-p=q-N$, $(p<q)$.

I'm not sure but this problem may be similar or related to Goldbach conjecture? Any proof/disproof, insight and opinion is appreciated, thanks.
4
votes
1answer
35 views

Is it impossible to recover multiplication from the division lattice categorically?

In this question it was asked if the division lattice (i.e., the preorder category $(\Bbb Z_{>0}, \mid)$) contains enough information categorically to recover the relation ...
5
votes
0answers
46 views

Integers which are the sum of non-zero squares

Lagrange's four-square theorem states that every natural number can be written as the sum of four squares, allowing for zeros in the sum (e.g. $6=2^2+1^2+1^2+0^2$). Is there a similar result in which ...