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

learn more… | top users | synonyms (1)

0
votes
2answers
30 views

If $p$ and $q$ are positive prime numbers such that $p$ is divisible by $q$, show that $p = q$.

To solve this problem, this is my approach. Assume $p\mid q$, there exists an $n∈N$ and assume $q\mid p$, there exists an $m∈N$. This would mean that $p=qn$ and $q=pm$. Then using substitution, ...
1
vote
2answers
39 views

$7^{6} | (a+b+ab)^2$ Find the value of $a,b$ [on hold]

$7^{6} | (a+b+ab)^2$ Find the value of a,b. I got this question as challenge from a friend of mine. Now he suggested me to go through Arthur Engel Book for Olympiads. But after going through the ...
0
votes
0answers
13 views

Does anyone know a reference to best-fitting lines with integral coefficients?

I'm writing up a manual on how to generate "nice" Linear Algebra problems; that is, where the solutions tend to be integral. I "discovered" the following fact about the best-fitting line: Theorem. ...
0
votes
1answer
22 views

The product of any two even integers is a multiple of 4

The product of any two even integers is a multiple of 4." This is what I have so far: let n, m be even integers and let D be a integer that is divisible by 4. n=2k. m=2l. d=4p. such that k,l,p ...
1
vote
1answer
30 views

Prove that $\sum^{P}_{k=1} \lfloor\frac {ka}{p}\rfloor = \frac{p^{2} - 1}{8} + \mu(a,p)$ mod$(2)$

I can prove that $\sum^{P}_{k=1} \lfloor\frac {ka}{p}\rfloor = \mu(a,p)$ mod$(2)$ where $p$ is an odd prime, $P = \frac {p-1}{2}$, $a$ is an integer not divisible by $p$, and $\mu(a,p)$ is the ...
0
votes
1answer
20 views

Let $5 \leq k < n$. Then $2k$ divides $n(n - 1)… (n - k + 1)$. What should I use permutations or polynomials?

Let $5 \leq k <n$. Then $2k$ divides $n(n-1)\cdots(n-k + 1)$. Is it true? Please provide a proof. I am confused about using induction, polynomial properties or permutations to solve this problem.
1
vote
1answer
24 views

The prime counting function has a lower bound of $C\log\log x$

I read that using Euclid's Theorem and by induction, a "gross underestimation" of the Prime Counting Function $\pi(x)$ can be stated as $C \log \log X$, i.e there is a constant $C$ such that the ...
3
votes
0answers
38 views

Combinatorics and geometry basic

Let $A$ be a set of $n$ points in the plane such that, for each point $P \in A$, $P$ is equidistant to at least $k$ other points in $A$. Show that $k < \frac{1}{2} + \sqrt{2n}.$ Can anyone help me ...
0
votes
0answers
19 views

A set A is infinite iff there exists a bijection from A to a proper subset of A

Below is the proof I have in my book for the first part of supposition. Let A be a set. First suppose A is infinite. By the proposition saying "Every infinite set contains an infinite subset that ...
28
votes
4answers
3k views

Are there an infinite number of prime numbers where removing any number of digits leaves a prime?

Suppose for the purpose of this question that number $1$ is a prime number. Consider the prime number $311$. If we remove one $1$ from the number we arrive at the number $31$ which is also prime. If ...
3
votes
1answer
26 views

$\frac {2 \cdot 3^{m + 1}}{k} - \frac {2 \cdot 3^{m}}{k + 1} \in \Bbb N_+$, find all possible values of $k, m$.

If $$\frac {2 \cdot 3^{m + 1}}{k} - \frac {2 \cdot 3^{m}}{k + 1} \in \Bbb N_+$$ and $$\frac {2 \cdot 3^{m}}{k} - \frac {2 \cdot 3^{m}}{k + 1} \le 1$$ where $k, m \in \Bbb N_+$ and $k \ge 2$, find all ...
1
vote
0answers
315 views

Number Theory Prove $\gcd(a, b, c)=\gcd(\gcd(a,b),c)=\gcd(\gcd(a,c),b)=\gcd(\gcd(b,c),a)$.

Let $a, b, c$ be integers, no two of which are zero, and $d=\gcd(a, b, c)$. Show that $d=\gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c))=\gcd(\gcd(a,c),b)$. Here is what I have tried, but I'm unsure if the part ...
0
votes
1answer
14 views

Find elements of a set that divide an expression.

I have to determine the elements of the following set: $A = \{x\in\ \mathbb Z \vert \sqrt[3]{\frac {7x + 2}{x+5}} \in \mathbb Z \}$ I know that $x+5 \not=0$ and $x+5$ must divide $7x + 2$ but I ...
1
vote
3answers
55 views

$x^2+y^2=2z^2$, positive integer solutions

Determine all positive integer solutions of the equation $x^2+y^2=2z^2$. First I assume $x \geq y$, and I have $x^2-z^2=z^2-y^2$. Then I have $(x-z)(x+z)=(z-y)(z+y)$, but from here, I don't know how ...
-1
votes
0answers
26 views

Number theory about lehmers equations [on hold]

1) Find $n$ such that $\phi(n)$ divides $n-2$ 2) Find $n$ such that $\phi(n)$ divides $n+2$ 3) find $n$ such that $\phi(n)$ divides $2n\pm 2$ 4)find $n$ such that $\phi(n)$ divides $8n \pm 2$
2
votes
0answers
14 views

If $a\not\equiv 0\mod{p}$ then there are $p-1$ solutions (ordered pairs) to $x^2-y^2\equiv a\mod{p}$

Let $p$ be an odd prime, and let $a\in\mathbb{Z}_p$ such that $a\not\equiv 0$. I need to show that there are $p-1$ ordered pairs $(x,y)$ such that $x^2-y^2\equiv a \mod{p}$. As I see it, the ...
0
votes
2answers
50 views

Determine $x$ if $x = 4 \mod 17$ and $x = 3 \mod 11$. [on hold]

Given $x =4\mod 17$ and $x = 3\mod 11$, determine $x$. I know that $\gcd(17,11)= 1$. I was hoping to use this to determine $x$.
1
vote
2answers
15 views

Prove that if $ab \equiv cd \pmod{n}$ and $b \equiv d \pmod n$ and $\gcd(b, n) = 1$ then $a \equiv c \pmod n$.

Prove that if $ab \equiv cd \pmod{n}$ and $b \equiv d \pmod n$ and $\gcd(b, n) = 1$ then $a \equiv c \pmod n$. From this we know that $\gcd(d, n) = 1$. I can't derive anything else. Please help. ...
0
votes
2answers
26 views

How many people are in the room?

The ratio of men to women is $3:4$, the ratio of Americans to non-Americans is $7:2$, and the number of people that are in the room is less than $100$. How many people are in the room? I am helping ...
6
votes
1answer
34 views

Can I apply Chinese remainder theorem here?

A number when divided by a divisor leaves $27$ remainder. Twice the number when divided by the same divisor leaves a remainder $3$. Find the divisor. My attempt: Let, the number be=$n$ and the ...
4
votes
3answers
103 views

$\frac{2abc}{(a+b-c)(b+c-a)(c+a-b)}$ a positive integer

Find all triplets $(a,b,c)$ of positive integers so that $\gcd(a,b,c)=1$ and $$ \frac{2abc}{(a+b-c)(b+c-a)(c+a-b)} $$ is a positive integer. What I've done: first I looked with Mathematica for ...
0
votes
0answers
48 views

Let $N = 3^{1000}\cdot 2^{2000009} +1.$ If $5^{\frac{N-1}{2}} = -1 \pmod N$, then $N$ is prime. [on hold]

Let $N = 3^{1000}\cdot2^{2000009} +1.$ Also let $5^{\frac{N-1}{2}} = -1 \pmod N$. Then I want to prove that $N$ is prime. Any help will be appreciated. Thank you very much.
0
votes
1answer
24 views

Simple question about divisibility and modular arithmetic

Is the following true? Fix an $n\in \Bbb N$ which is not a multiple of $5$. Then for every $l\in\{0,\cdots,n\}$ there exists a $k\in \Bbb N_0$ with $5k\equiv l \mod n$. If yes, how do we prove it?
-2
votes
1answer
36 views

Show that if $x = y + z$ , and $d$ is a divisor of any two of the integers $x$, $y$, and $z$, it is also a divisor of the third. [on hold]

How should I approach this problem and using what method to solve this problem? It seems so logical, but I can't seem to show how.
18
votes
5answers
2k views

Can n! be a perfect square when n is an integer greater than 1?

Can n! be a perfect square when n is an integer greater than 1? (But is it possible, to prove without Bertrand's postulate. Because bertrands postulate is quite a strong result.)
1
vote
2answers
409 views

Find all positive integers solution of $xy+yz+xz = xyz+2$

1.Find all positive integers solution $xy+yz+xz = xyz+2$ 2.Determine all p and q which p,q are prime number and satisfy $p^3-q^5 = (p+q)^2$ Thx for the answer 3.Find all both positive or ...
6
votes
2answers
477 views

Diophantine Equations : Solving $a^2+ b^2=2c^2$

I was working through some number theory problems , when I came across the following question : Find all solutions of $a^2+b^2=2c^2$ My Solution (Partial) : We can rewrite the above ...
1
vote
1answer
72 views

Parametric characterization for $x^2 + y^2 = 2z^2$

What would be a parametric characterization of all relatively prime solutions in positive integers to $x^2 + y^2 = 2z^2$? The hint I got was: Show there are integers $a$ and $b$ for which $x = a+b$ ...
0
votes
0answers
14 views

Transformations between Pell[-like] equations

I’m looking for [non-trivial] transformations that take a Pell-like equation $$ u^2-dv^2=w $$ and turn it into another Pell-like equation $$ x^2-my^2 = z. $$ Best-case scenario, one could always use ...
2
votes
1answer
43 views

Every subset of a finite set is finite

Is there anyway I can prove this statement using the pigeonhole principle below? "If A,B are sets and B is finite, and there is an injection $f : A \rightarrow B$, then A is finite and $Card(A)\leq ...
1
vote
2answers
20 views

Find all prime p such that Legendre symbol of $\left(\frac{10}{p}\right)$ =1

In the given question I have been able to break down $\left(\frac{10}{p}\right)$= $\left(\frac{5}{p}\right)$ $\left(\frac{2}{p}\right)$. But what needs to be done further to obtain the answer.
0
votes
2answers
45 views

Prove that for every integer $n$ there exists a unique integer $m$ such that $2m + 8n = 6$.

Prove that for every integer $n$ there exists a unique integer $m$ such that $2m + 8n = 6$. My method: Let $n$ be given. We know that $2m + 8n = 6$. Then $2m = 6 - 8n$. Thus, $m = 3 - 4n$. I am ...
0
votes
1answer
32 views

$n \equiv 7 \pmod{8}$, prove $\sigma(n) \equiv 0 \pmod{8}$

Let $\sigma(n)$ denote the sum of all divisors of $n$. If $n \equiv 7 \pmod{8}$, show that $\sigma(n) \equiv 0 \pmod{8}$. If $n$ is prime, by definition, $\sigma(n)=n+1\equiv 0\pmod{8}$. But how ...
0
votes
5answers
32 views

Let a and b be positive integers and suppose that, for every positive integer c, we have that $a\equiv b\pmod c$. Then, $a=b$.

Let c be any positive integer. Suppose $a\equiv b\pmod c$. Then, $c\mid b-a$. Now what? I feel like I only have one tool at my disposal, namely divisibility: to say that $c\mid b-a$ means that ...
0
votes
0answers
12 views

Looking for a simpler solution to a problem about the divisibility of combinatorial numbers

Here is the problem: For every positive integer r, there exists a natural number $n_r$ such that for every integer $n>n_r$, there is at least one $k$, where $1\leq k \leq n-1$,such that ...
1
vote
0answers
20 views

Summing the digits of sum of the digits to obtain prime numbers

Define sum of digits (in base $10$) function as $sd_{10}(n)=\sum_{i=0}^ma_i$ where $n=\sum_{i=0}^ma_i \cdot 10^i$ and $0\le a_i\le 9$. If we choose prime number $86423$ and sum its digits we obtain a ...
0
votes
0answers
11 views

Reference for zero sum problems?

I am looking for books/ references which deal with the analysis of zero sum problems and weighted zero sum problems. I have found some articles on the internet, but they seem insufficient. Any ...
9
votes
2answers
101 views

Why is the Fundamental Theorem of Arithmetic so important?

I've recently read about the Fundamental Theorem of Arithmetic and I think that I have just about understood the proof. What I found quite interesting at first was the "Fundamental" part in the name. ...
2
votes
0answers
17 views

Seeking for an examples of non-trivial sets that can be used to generate all the natural numbers

First, let us remind ourselves of the Lagrange`s four square theorem which states that every natural number can be written (represented) as the sum of four integer squares. Since we have $(-a)^2=a^2$ ...
4
votes
1answer
41 views

Fractions of powers of primes.

I'm wondering whether the following statement is true: Let $p$ and $q$ be two prime numbers (or more generally let $p$ and $q\neq 0$ be integers with $\gcd(p,q)=1$). Then for all $\varepsilon >0$ ...
1
vote
2answers
14 views

Can the state of a system after applying the operation “absolute value” be got back using elementary operations or transformations?

Take the operation or transformation "addition". You can get back the original state of the system by doing the opposite operation, i.e., "subtraction". But, if the operation is "absolute value", you ...
1
vote
1answer
44 views

Find how many solutions the congruence $x^2 \equiv 121 \mod 1800$ has

I want to find how many solutions the congruence $x^2 \equiv 121 \mod 1800$ has. What is the method to find it without calculating all the solutions? I can't use euler criterion here because 1800 ...
-1
votes
0answers
19 views

Number of ways to write $n \in \Bbb N$ as a sum of $k$ positive integers? [on hold]

For example: The number of ways to write $6$ as a sum of $6$ positive integers is $1$ which is $1+1+1+1+1+1$. And the number of ways to write $10$ as a sum of $2$ positive integers is $5$. I need the ...
0
votes
1answer
30 views

Elementary number theory with some arithmetic progression.

Let A={n∈N┤n is the sum of seven consecutive integers}. B={n∈N┤|n is the sum of eight consecutive integers}. C={n∈N┤|n is the sum of nine consecutive integers}. Find A∩B∩C. I tried ...
2
votes
1answer
42 views

Looking for a simpler solution about quadratic congruence

Here is the Problem: 1)Suppose $p$ is a prime. prove that for any integer $k$, there exist integers $x$ and $y$ such that $x^2+y^2 \equiv k\ \pmod p$. 2)Are there infinitely many composite ...
2
votes
1answer
48 views

prove C is a proper subset of ℕ. Then prove ℕ is infinite.

Please, can you help me to do this? Let $C =\{n + n \;|\; n\in \mathbb{N} \}$, and define $f:\mathbb{N}\to C$ by $f(n) = n + n$. First prove $C$ is a proper subset of $\mathbb{N}$. Then prove ...
1
vote
0answers
27 views

For how many n's less than 100 do we have $s(n)=s(n+i)$

We define $s(n)$ as $LCM(least\ common\ multiplier)$ of numbers $1\ through\ n$. For how many $n's $ less than $100$ do we have: $s(n)=s(n+i),(i$ is a positive integer less than $10)??$ I have ...
0
votes
1answer
55 views

If $d>1$ is a squarefree integer, show that $x^2 - dy^2 = c$ gives some bounds in terms of a fundamental solution.

If $d>1$ is a squarefree integer, show that $x^2 - dy^2 = c$ gives some bounds in terms of a fundamental solution. I am not able to understand the question itself. What does it exactly mean ...
0
votes
2answers
34 views

Can you show that $3n+1$ is not divisible by $5$ using congruences?

I'm trying to prove that the difference of two consecutive cubes is never divisible by $5$, and I got to a point where I would have to prove that $3n+1$ is not divisible by $5$, where n is an integer. ...
0
votes
1answer
9 views

On the relationship between $\max(p_i)$ and $\omega(b)$, if $\sigma(b^2)/b^2$ is bounded above by a specific number $U$

Let $\omega(x)$ denote the number of distinct prime factors of $x$, and let $\sigma(x)$ be the sum of the divisors of $x$. Denote the abundancy index of $x$ by $I(x) = \sigma(x)/x$. Let the number ...