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

learn more… | top users | synonyms (1)

4
votes
3answers
87 views

Prove $\log_7 n$ is either an integer or irrational

I have been trying to prove a certain claim and have hit a wall. Here is the claim... Claim: If $n$ is a positive integer then $\log_{7}n$ is an integer or it is irrational Proof ...
-1
votes
2answers
32 views

How many ways to arrange colors (constraints)

Ed has five identical green marbles and a large supply of identical red marbles. He arranges the green marbles and some of the red marbles in a row and finds that the number of marbles whose right ...
2
votes
4answers
67 views

Number of Interesting Quadruples

Define an ordered quadruple of integers $(a, b, c, d)$ as interesting if $1 \le a<b<c<d \le 10$, and a+d>b+c. How many interesting ordered quadruples are there? This is a bit of trouble ...
2
votes
1answer
62 views

strange fibonacci recurrence

As it is well known fibonacci numbers satisfy the recurrence relation $$F_{n}=F_{n-1}+F_{n-2}$$ with initial conditions $F_{0}=0$ and $F_{1}=1$. While playing around with numbers,I noticed the ...
0
votes
0answers
39 views

What is Lebesgue measure of sets of inverse prime numbers in $[0,1] $?

I would like to know if it is possible to know the lebesgue mesure of sets of inverse prime numbers in $[0,1]$ Note : I think should to know in the first if the sets of primes are infinit countable ...
2
votes
1answer
50 views

Prove that $4$ divides $n$ [duplicate]

Let $a_1$,$a_2$,$a_3$,.......,$a_n$ be $n$ such that each $a_i$ either $1$ or $-1$.If $a_1 a_2 a_3 a_4+a_2 a_3 a_4 a_5+......+a_n a_1 a_2 a_3=0$, then prove that $4$ divides $n$. I tried this for ...
1
vote
2answers
82 views

Is $2^n-1$ always a prime for odd values of $n$? [duplicate]

Is $2^n-1$ always a prime for odd values of $n$? $n\not=1$ Taking some odd values of $n$, I observed outcome is coming as a prime number. How to verify it? Or at-least, is $2^n-1$ always coprime to ...
0
votes
1answer
37 views

if $n > 1$ is an integer not of the form $6k + 3$, prove that $n^2 + 2^n$ is composite.

My proof. By Division Algorithm, n is one of form $6 k, 6 k+1, 6 k+2, 6 k+4, 6 k+5$. So first, If $n=6 k$, $n^2+2^n=36 k^2+2^{6 k}$. then $2$ divide it. and, divisor is not one. so, it is composite. ...
2
votes
2answers
39 views

Show that 7 is a primitive root modulo 601

How do you show that 7 is a primitive root modulo 601 without having to do many, many congruences? I'm sure there is an easier way and I should like very much to learn it.
2
votes
2answers
35 views

Prove that either the average of the numbers $a_{1}, a_{2},…, a_{n}$

Let $a_{1}, a_{2},..., a_{2n}$ be positive real numbers such that $a_{j}a_{n+j}=1$ for the values $j=1,2,...,n$ ($a$) Prove that either the average of the numbers $a_{1}, a_{2},..., a_{n}$ is ...
3
votes
1answer
33 views

Prove for primes p $>2$ that $\sum_{k=1}^{p−1}{k^{2p−1}}\equiv\frac{1}{2}p(p+1)\pmod {p^2}$

Let $p$ be an odd prime. Prove that: $$\sum_{k=1}^{p−1}{k^{2p−1}}\equiv\dfrac{p(p + 1)}{2}\pmod {p^2}$$ The problem is taken from the 2004 Canada National Olympiad. I am only able to show ...
114
votes
20answers
9k views

Mental Calculations

This is the famous picture "Mental Arithmetic. In the Public School of S. Rachinsky." by the Russian artist Nikolay Bogdanov-Belsky. The problem presented on a blackboard requires computing the ...
0
votes
1answer
79 views

Least prime number proof [closed]

Prove that 2 is the only even prime number. I know that 2 is the only even prime number. I am curious to prove it
-1
votes
2answers
39 views

Last digit of a perfect square must be $0, 1, 4, 5, 6,$ or $9$ [closed]

We know that a perfect square number can contain 0,1,4,5,6 and 9 in its unit place. How can I prove that a perfect square number cannot contain 2,3,7 and 8 in its unit place?
1
vote
1answer
40 views

Is my proof for this fact correct?

The thing ought to be proven Let $a$ and $b$ be nonzero integers that are relatively prime, and let $c$ be an integer. Show that $ax+by=c$ has an integer solution. My postulated proof that ought ...
0
votes
3answers
40 views

Prove n is a product of a square and a cube

Suppose $n\ge 2$ is an integer with the property that whenever a prime $p$ divides $n$, $p^2$ also divides $n$ (i.e., all primes in the prime factorization of $n$ appear at least to the power ...
3
votes
3answers
64 views

Let $(a, b, c)$ be a Pythagorean triple. Prove that $\left(\dfrac{􀀀c}{a}+\dfrac{􀀀c}{b}\right)^2$ is greater than 8 and never an integer.

Let $(a, b, c)$ be a Pythagorean triple, i.e. a triplet of positive integers with $a^2 + b^2 = c^2$. a) Prove that $$\left(\dfrac{􀀀c}{a}+\dfrac{􀀀c}{b}\right)^2 > 8$$ b) Prove that ...
0
votes
2answers
49 views

Distinguishable Objects in a Circular Arrangement

I asked a question, AOPS Math Jam If you look at #9: **Please CTRL:F -> ** this: *"Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least ...
0
votes
1answer
51 views

Expression of theorem by $p\Rightarrow q$ [closed]

$\sqrt 2$ is irrational. Is it true that i express this theorem in this way?: If $\sqrt 2$ is a real number, then it is irrational. Is there any better way to express this theorem by $p\Rightarrow q$? ...
4
votes
3answers
53 views

What is the minimum number of moves to change $a$ into $b$ by doubling and halving?

We are given integers $a$ and $b$, and wish to change $a$ to $b$ using these operations: (1) Map $a \mapsto \lfloor \frac{a}{2} \rfloor$. (If $a$ is even, replace it with $\frac{a}{2}$. If $a$ is ...
4
votes
2answers
48 views

Find all $n \in \mathbb{Z}_{>0}$ such that $n^2+a \mid n^3+a$

Could anyone advise me how to find all $n \in \mathbb{Z}_{>0}$ such that $n^2+a $ divides $ n^3+a,$ where $a \in \mathbb{Z} \setminus \{0\}$ is fixed ? I have checked it is necessary that $n^2+a $ ...
2
votes
1answer
30 views

The diophantine problem for $R[T]$ is solvable iff the diophantine problem for $R$ is solvable

One part of the paper that I am reading is the following: Let $R$ be a commutative ring with unity and let $R'$ be a subring of $R$. We say that the diophantine problem for $R$ with coefficients ...
3
votes
0answers
52 views

Equal partial sums of $k$ numbers of $1$ to $k$

There are two sequences of $k$ numbers, denoted as $a_{i}$ and $b_{i}$, $i\in [1,k]$. Each number is between $1$ and $k$, namely $a_{i}\in [1,k]$, $b_{i}\in [1,k]$, $\forall i\in [1,k]$. Prove that ...
2
votes
1answer
18 views

Necessary condition for a finite cyclic sum of length $4$ made of $1$ and $-1$ to be $0$

This is something I observed when I was reading the classic Problem-Solving Strategies by Arthur Engel. I liked the way he solved the following problem: Let $a_1,\ldots,a_n\in\{-1,1\}$ such that ...
0
votes
1answer
46 views

Find the smallest positive integers $a, b$ such that…

Find the smallest positive integers $a, b$ such that: i) $|a - b| = 3$ ii) the sum of digits of each of $a, b$ is divisible by $11$
2
votes
2answers
83 views

Solution to equation $4n+1 = (2k+1)^2-(2u)^2$ over the natural numbers(!)

Let $n \in \mathbb{N}$ be given, then I want to know if there are $k ,u \in \mathbb{N}$ (with $k \neq n, u \neq n$) such that $4n+1 = (2k+1)^2-(2u)^2$ holds. What makes it difficult for me is the ...
0
votes
2answers
35 views

If $p_i$ is prime then $p_i \Bbb Z \cap p_j \Bbb Z= \emptyset \ \forall i,j \in \Bbb N, i\neq j$.

If $p_i$ is prime then $p_i \Bbb Z \cap p_j \Bbb Z= \emptyset \ \forall i,j \in \Bbb N, i\neq j$. Where $a \Bbb Z=\{x\in \Bbb Z: x=0 \mod a\}$. I ran into some problem where having this lemma proved ...
1
vote
0answers
24 views

Mersenne semiprimes with square indices

A Mersenne semiprime is a semiprime of the form $2^n-1$, it can be shown that $2^n-1$ can be a semiprime if and only if $n$ is either a prime or a square of a prime. There are plenty Mersenne ...
1
vote
1answer
36 views

Solve the system of congruences (CRT)

$$560x \equiv 1 \pmod{3, 11, 13}$$ I found a few (by trial and error) $560x \equiv 1 \pmod{13} \implies x = 1 + 13k$. $560x \equiv 1 \pmod{3} \implies x = 2 + 3k$. $560x \equiv 1 ...
3
votes
3answers
59 views

Solve the following simple congruence

$$560x \equiv 1 \pmod{429}$$ I am close, I used Euclid's algorithm but the remainder is hard to go backwards. $$560 = 1(429) + 131 $$ $$429 = 3(131) + 36$$ $$131 = 3(36) + 23$$ $$36 = ...
3
votes
4answers
240 views

Integer solutions using PIE

Find the number of integer solutions to $a+b+c+d=18$ with $ 0≤a,b,c,d≤6$. With no restrictions there are: $$\binom{21}{3} = 1330$$ Ones that are invalid are: $a, b, c, d \ge 7$. But how do I ...
0
votes
1answer
47 views

Find the number of polynomials satisfying the root conditions

Let $S$ be the set of all polynomials of the form $z^3+az^2+bz+c$, where $a$, $b$, and $c$ are integers. Find the number of polynomials in $S$ such that each of its roots $z$ satisfies either ...
7
votes
2answers
111 views

First-order definition of nonnegative in integers

Given the structure $(\mathbb Z,+,-,\times,0,1)$, what's the easiest way to write "$x\ge0$" in that structure? I know that this works: $$\exists a\exists b\exists c\exists d,a^2+b^2+c^2+d^2=x$$ ...
5
votes
4answers
141 views

How do I find the remainder of $4^0+4^1+4^2+4^3+ \cdots + 4^{40}$ divided by 17?

Recently I came across a question, Find the remainder of $4^0+4^1+4^2+4^3+ \cdots + 4^{40}$ divided by 17? At first I applied sum of G.P. formula but ended up with the expression $1\cdot ...
1
vote
0answers
26 views

Rational analogue of expansion to base b

As is well known, we can expand every positive integer $n$ to a base $b \in \Bbb N$ in the form $$n = \sum_i a_ib^i ,\ \ \ 0\leq a_i \leq b_i-1$$ uniquely. Less well known is that we can do this for ...
1
vote
1answer
88 views

Let $p, q$ be odd primes. Find the largest integer $n$ such that there exists an integer $a$ with $\gcd(a, pq) = 1$ with order equal to $n \bmod pq$.

How to find the largest integer $n$ here? I'm not sure how to start it. Thank you very much!
6
votes
4answers
150 views

Proving that cows have same weight without weighing it!

My friend gave me this problem and I have no clue how to go about it: A peasant has $2n + 1$ cows. When he puts aside any of his cows, the remaining $2n$, can be divided into two sub-flocks of $n$ ...
1
vote
4answers
147 views

Sum of non-real roots of equation?

What is the sum of all non-real, complex roots of this equation - $$x^5 = 1024$$ Also, please provide explanation about how to find sum all of non real, complex roots of any $n$ degree polynomial. ...
-3
votes
1answer
45 views

How many computational steps to determine $\pi(x)$ at $x=10^{12}$? [closed]

Just like the title says, how many actions are required by a computer (or a person) to determine $\pi(x)$ at $x$ equals $10^{12}$ with the most modern method?
0
votes
0answers
48 views

NT problem (use mod) Solve this equation

This might not be solvable, but my NT teacher wanted us to give it a try. Solve $x_1^4 + x_2^4+\cdots+x_7^4 = 1\,000\,007$. What has been figured out so far: Mod 8 to get the equation = 7 (mod ...
4
votes
4answers
151 views

Prove that $2730$ divides $n^{13} - n$ for all integers $n$. [duplicate]

Prove that $2730$ divides $n^{13} - n$ for all integers $n$. What I attempted is breaking $2730$ into $2, 3, 5$, and $7, 13$. Thus if I prove each prime factor divides by $n^{13} - n$ for all ...
1
vote
1answer
65 views

Wilson's Theorem Factorial

I need to prove that $ (1 \cdot 3 \cdot 5 \dotsm 2009)^2 - 1 \equiv 0 \pmod{2011}$ By modular simplification, I need to prove that $(3 \cdot 5 \cdot 7 \dotsm 2009) \equiv 1 \pmod{2011}$ I know that ...
2
votes
1answer
28 views

Non-additive upper logarithmic density: $\ell^\star(X \cup Y) \neq \ell^\star(X)+\ell^\star(Y)$

Let $\ell^\star$ be the upper logarithmic density on the set of positive integers, namely $$ \forall X\subseteq \mathbf{N}^+, \,\, \ell^\star(X)=\limsup_n \frac{1}{\ln n}\sum_{x \in X\cap ...
0
votes
2answers
29 views

Finding a point of a rotation (complex numbers)

I posted early but got a very tough response. Point $A = 2 + 0i$ and point $B = 2 + i2\sqrt{3}$ find the point $C$ $60$ degrees ($\pm$) such that Triangle $ABC$ is equilateral. Okay, so I'll begin ...
30
votes
12answers
806 views

Is this $\gcd(0, 0) = 0$ a wrong belief in mathematics or it is true by convention?

I'm sorry to ask this question but it is important for me to know more about number theory. I'm confused how $0$ is not divided by itself and in Wolfram Alpha $\gcd(0, 0) = 0$ . My question here is: ...
6
votes
3answers
79 views

Prove : The polynomial has no integral roots. [duplicate]

Q. Prove that a polynomial $f(x)$,with integer coefficients has no integral roots if $f(0)$ and $f(1)$ are both odd integers. My attempt: Let $$f(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n$$ now $f(0)=a_0$ ...
2
votes
1answer
37 views

I have plugged $p/q$ into the equation. Not sure what to do next.

Suppose $a_0,a_1,\dots,a_n$are integers and $a_0\neq 0$ and $a_n\neq 0$.Consider the polynomial $f(x)=a_0x^n+a_1x^{n-1}+\dots+a_{n-1}x+a_n$. If $p\neq 0,q>0$ are coprime integers and $p/q$ ...
5
votes
2answers
41 views

For positive integers $x, y, k$, prove that $4^x (4^y+1)=k(k+1)$ implies $x = y$

In the proof that I read, even $k$ implies $4^x=k$ and $4^y+1=k+1$. I am wondering why we don't need to factorize $4^y+1$ into $pq$, such that $p, q > 1$, and solve for $4^x p=k$, $q=k+1$.
-1
votes
3answers
64 views

Using induction to prove that $2 \mid (n^2 − n)$ for $n\geq 1$

Use induction to prove that, for all $n \in \mathbb{Z}^+$, $2\mid (n^2 − n)$. That is, I am supposed to use induction to prove that $(n^2 − n)$ can be divided by $2$ when $n$ is a positive ...
2
votes
1answer
38 views

Let $p$ and $q$ be distinct primes. Can you prove the sequence $\{p^n\}_{n \in \mathbb{N}}$ is not Cauchy under the given metric on $\mathbb{Q}$?

This is an elementary $p$-adic theory question. Granted $d(x,y)=|x-y|_q$ is a metric on $\mathbb{Q}$, and $|\cdot|_q$ is a norm such that $$|x|_q=q^{-ord_q x}$$ where $ord_q x$ is the largest ...