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

learn more… | top users | synonyms (1)

6
votes
4answers
152 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
148 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
46 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
49 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
152 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
66 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
811 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
81 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
65 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 ...
4
votes
0answers
87 views

Integer solutions to the equation $a^3+b^3+c^3=30$

The following problem was posed to me but I could not do much about it: Determine if there are any integer solutions to the equation $a^3+b^3+c^3=30$ I made a computer search that shows that ...
3
votes
1answer
80 views

Are there infinitely many pythagorean triples?

I believe these questions are all asking different things, but: Are there infinitely many (integer) solutions to the pythagorean theorem? Is every positive integer part of a solution to the ...
2
votes
1answer
81 views

What is known about the minimal number $f(n)$ of geometric progressions needed to cover $\{1,2,\ldots,n\}$, as a function of $n$?

So a geometric progression can contain at most two primes. This automatically gives a lower bound on the minimal number $f(n)$ of geometric progressions needed to cover the integers ...
18
votes
3answers
282 views

Is it possible to cover $\{1,2,…,100\}$ with $20$ geometric progressions?

Recall that a sequence $A=(a_n)_{n\ge 1}$ of reals is said to be a geometric progression whenever $a_{n+1}/a_n$ is constant for each $n\ge 1$. Then, replacing $20$ with $12$, the following question ...
3
votes
3answers
46 views

Solving simple mod equations

Solve $3x^2 + 2x + 1 \equiv 0 \mod 11$ Additionally, I have an example problem, but a step in the middle has confused me: $3x^2 + 5x - 7 \equiv 0 \mod 17$. Rearrange to get $3x^2 + 5x \equiv 7 \mod ...
7
votes
6answers
485 views

I'm trying to encode a number. [closed]

Pulling a prank on a friend who brags is really good at math. Need an complex equation where the answer will work out to 1346 in some context. Any help would be appreciated.
1
vote
0answers
58 views

Integer $2n^2+2$ as the sum of 2,3,4, and 5 squares

If $n-1$ and $n+1$ are both primes, establish that the integer $2n^2+2$ can be represented as the sum of 2, 3, 4, and 5 squares. I managed to solve 2 and 4 squares, since: $$2n^2+2 = ...
7
votes
0answers
127 views

Conjectured compositeness tests for $N=b^n \pm b \pm 1$

How to prove that these conjectures are true ? Definition : $\text{Let}~ P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)~ , \text{where}~ m ...
0
votes
0answers
35 views

Show that for no positive integer $n$ we can have $\phi(n) = n/4$ or $\phi(n) = n/5$ [duplicate]

Show that for no positive integer $n$ we can have $\phi(n) = n/4$ or $\phi(n) = n/5$. I understand why we can't have $\phi(n) = n/4$ or $\phi(n) = n/5$ however I don't know how to show this.
2
votes
1answer
51 views

The definition of rational numbers

Very often I find this definition of rational numbers in my textbooks: A rational number is a number determined by the ratio of some integer p to some nonzero natural number q. But numbers ...
0
votes
1answer
65 views

How to show that we reach $1$ at an odd or even turn without brute force

Consider the following challenge between two players A and B. They are given the initial terms $a_0= 3^{2014}$ and $b_0= 15^{4028}$ of two sequences, and the scope is to reach $1$ before the other, ...
0
votes
1answer
32 views

What does Residue multiplication mean?

Suppose $ a, b, c, n \in \mathbb{Z}, \qquad$ where $n>0, \qquad$ then $a\cdot b \texttt{ mod } n = c$ is called modular multiplication. The article that I am reading mentions Modular and Residue ...
0
votes
2answers
47 views

Clarification about the concept of number

I am reading a book called Numerical Notation: A Comparative History (by Stephen Chrisomalis). The first chapter (Introduction), second and third paragraph go like this: If you look up from this ...
1
vote
1answer
32 views

How to find the These numbers?

Suppose $n \in N$. $n$ can be described as the sum of square of three number's. That is $ n = a^2 + b^2 + c^2$ . My Question is: How to find $a, b, c$?
0
votes
1answer
23 views

How to show that $\prod^{p-1}\limits_{j=0} (x+\eta^jy)=x^p+y^p$

How to show that $\prod^{p-1}\limits_{j=0} (x+\eta^jy)=x^p+y^p$, where $p$ is an odd prime, $\eta$ is $p$-th roots of unity and $x,y$ are integers. It could be reduced to the form ...
8
votes
3answers
682 views

Sums of Fourth Powers

While fooling around on my calculator I found: $$7^4 + 8^4 + (7 + 8)^4 = 2 * 13^4$$ $$11^4 + 24^4 + (11 + 24)^4 = 2 * 31^4$$ I'm intrigued but I can't explain why these two equations are true. Are ...
39
votes
4answers
944 views

Rational solutions to $a+b+c=abc=6$

The following appeared in the problems section of the March 2015 issue of the American Mathematical Monthly. Show that there are infinitely many rational triples $(a, b, c)$ such that $a + b + ...
1
vote
1answer
73 views

Number of zeros at the end of $k!$

For how many positive integer $k$ does the ordinary decimal representation of the integer $k\text { ! }$ end in exactly $99$ zeros ? By inspection I found that $400\text{ !}$ end in exactly $99$ ...
4
votes
1answer
56 views

$\lfloor x^k \rfloor \equiv m \pmod{n}$ with $x$ irrational

Let $x>1$ be an irrational number, and $n$ a positive integer. Is it true that, for each integer $m$, there exists an integer $k$ such that $$ \lfloor x^k \rfloor \equiv m \pmod{n}? $$
-1
votes
0answers
35 views

How can I use diophantine approximation to find a real number?

I have been told that the following question can be solved using Diophantine approximation, but I cannot find a way to solve it. I have no prior knowledge of Diophantine approximation and so I ...
14
votes
1answer
1k views

Two numbers that cannot both be squares

I was wondering where to start with the following question: Show for $a,b \in \mathbb{N}$ that $a+b^2$ and $a^2+b$ cannot be both squares. Here $\mathbb{N}$ is the positive integers ($0$ not ...
0
votes
1answer
32 views

What is the size of Range?

Suppose d=gcd$(a,n)$ where $a, n \in \mathbb{Z}, n>0$ and $f_a: \mathbb{Z_n} \to \mathbb{Z_n} \\ \qquad x \to ax\texttt{ mod } n$ The size of Domain is evident and for the size of Range my ...
-2
votes
3answers
55 views

Smallest number that is divisible by $7$ and leaves a remainder of of $1$ when divided by $2, 3, 4, 5,$ or $6$ [closed]

A number, when divided by 2, 3, 4, 5, or 6, leaves 1 as remainder, while the same number leaves no remainder when divided by 7. What is the least number with these properties? The answer is 301. ...
5
votes
1answer
206 views

Wilson's Theorem - Why only for primes? [closed]

Why is it true that Wilson's Theorem only holds for prime numbers? I read a proof of it, and it did not seem to cater to that aspect of the theorem.
17
votes
6answers
6k views

Can you complete the expression $2 \underline{ }\, \underline{ }\, \underline{ } \,\underline{ } 5 = 2015$?

Can you complete the expression $2 \underline{ } \, \underline{ }\, \underline{ } \, \underline{ } 5 = 2015$ and make it correct by replacing two underscores with a selection of the ...
0
votes
2answers
25 views

Inequality involving floor

Let $x$ be randomly chosen from $\{1,...n\}$. Define $X_{p}$ such that \begin{equation} X_p= \begin{cases} 1, & \text{if}\ p|x, \\ 0, & \text{otherwise.} ...
0
votes
0answers
19 views

Is $\sum\limits_{{\rm{i}} = 1}^{n - k} {{b_i}} \times {b_{n-2}} + b_{k}$ correct to express this pattern in base n?

having seen the pattern be,ow i have tried to express it in base n, of course there should be few constraints added to parameters. $$\begin{align} 1 \times 8 + 1 &= 9\\ 12 \times 8 + 2 &= ...
1
vote
0answers
21 views

Simple clarification- big $O$ and small $O$ notations in Erdos-Kac theorem proof

From The Probabilistic Method by Alon and Spencer. Let $\nu(n)$ be the number of primes $p$ dividing $n$ and set \begin{equation} X_p= \begin{cases} 1, & \text{if}\ p|x, \\ ...
0
votes
6answers
263 views

Alternate ways to prove that $4$ divides $5^n-1$

I was working for various method to solve this: For all $n\in \mathbb N$: $4\;\mid\;(5^{n}-1)$. My try was: 1st: $$n=1 \to 4|5^1-1\\n \geq 2 \to 5^n=25,125,625,3125,...\\ n\geq 2 \to ...
1
vote
2answers
73 views

Seating people in a circular table

It has always been an interesting question. If we have $10$ chairs and a round table, how many ways are there of seating $10$ people? I would say there are $10!$ ways to seat the people due to ...
8
votes
3answers
102 views

How to prove there are no solutions to $a^2 - 223 b^2 = -3$.

As the title suggests, I'm trying to prove that there are no solutions to $a^2 - 223b^2 = -3$ (with $a,b\in \mathbb{Z}$). Ordinarily, taking both sides $\mod n$ for some clever choice of $n$ proves ...
-1
votes
2answers
36 views

Does the order in a circular arrangement matter?

I posted a question a while ago: Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs. My question here is: imagine a ...
4
votes
1answer
74 views

Solution to Diophantine equation $\frac{1}{x^2}+\frac{1}{y^2}=\frac{1}{z^2} $

I have to prove the following, but I don't know how to start. The only solutions in positive integers of the equation $$ \frac{1}{x^2}+\frac{1}{y^2}=\frac{1}{z^2} \qquad \gcd(x,y,z)=1 $$ ...
21
votes
4answers
1k views

Visualizing the factorial

Often in basic mathematics, we can visualize things very easily, which I believe helps understanding (instead of just working out a number theoretical proof). For example: $$(n+1)^2 - n^2 = (n+1) +n$$ ...
3
votes
1answer
35 views

How many pairs of $(x, y)$ satisfied this equation

I need help to solve in $\mathbb{Z}$ the following equation $$yx^{2}+xy^{2}=30$$ I tried to solve it by factor $30$ to $5\times 6$ and I get those two pairs $(2, 3) \& (3, 2) $... is their any ...
2
votes
2answers
392 views

Stars and Bars vs PIE

I randomly made up this question so I could check: There are $3$ kids and $6$ gifts, how many ways to distribute so that each kid has at least one gift. Obviously, $**|**|**$ there are ...