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

learn more… | top users | synonyms (1)

0
votes
2answers
34 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
24 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$?
37
votes
5answers
811 views

Is ${F_{n}}^2 - 28$ always a composite number?

The problem is as follows: Prove or disprove that if ${F_{n}}$ is $n$-th Fibonacci number, and $n>5$, than $${F_{n}}^2 - 28$$ cannot be a prime. I came across this problem accidentally ...
0
votes
1answer
20 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 ...
11
votes
1answer
118 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 + ...
4
votes
3answers
266 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 ...
13
votes
5answers
4k views

Can you complete the expression 2 _ _ _ _ 5 = 2015?

Can you complete the expression 2 _ _ _ _ 5 = 2015 and make it correct by replacing two underscores with a selection of the operational symbols $+, - , ...
2
votes
1answer
541 views

Find an inverse of $a$ modulo $m$ for each of these pairs of relatively prime integers

How would I find the inverse of a given number $a$ modulo $m$, given that $\gcd(a,m)=1$? a) $a = 2$, $m = 17$ $17 = 2 \cdot 8 + 1$ $2 = 1 \cdot 2 + 0$ $1 = 17 - 8 \cdot 2$ <-How do I know ...
1
vote
1answer
60 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$ ...
5
votes
1answer
193 views

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

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.
4
votes
1answer
46 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}? $$
19
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$$ ...
-1
votes
0answers
15 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
6answers
225 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 ...
0
votes
1answer
23 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 ...
0
votes
3answers
35 views

Divisibility puzzle

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. How ...
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 &= ...
3
votes
2answers
99 views

at least one of 100 consecutive integers is relatively prime to all natural numbers less or equal 100

For an arbitrary integer $n$ define $A_n=\{i|n \leq i \leq n+99 \text{ where }i\text{ is an integer}\}$ (i.e. $A_n$ is 100 consecutive integers) Is it true that for any integer $n$ there is an ...
0
votes
2answers
24 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.} ...
2
votes
1answer
26 views

For any $N$ and $B$, is there always a $B$-smooth relation $x + y \equiv 0 \pmod{N}$?

Let $N$ be any integer and $B \geq 2$ be a smoothness bound. Does there always exist $B$-smooth integers $x,y$ such that: $$x + y \equiv 0 \pmod{N}\text{ ?}$$ My only progress is that I know the ...
21
votes
6answers
3k views

Chicken Problem from Terry Tao's blog (system of Diophantine equations)

This problem was posted by Terry Tao in his blog earlier. It's actually from his son's Math Circle. It took him $15$ minutes to solve it. I guess we all can take a crack at it. Three farmers were ...
5
votes
3answers
80 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 ...
2
votes
3answers
189 views

Argue by contradiction : $n\in \mathbb N \to \; 4|(5^{n}-1)$ [closed]

I was working for various method to solve this :$n\in \mathbb N \to \; 4|(5^{n}-1)$ now I want to solve it only by "Argue by contradiction"
1
vote
0answers
20 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, \\ ...
-1
votes
2answers
30 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 ...
1
vote
2answers
47 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 ...
-2
votes
3answers
65 views

Division problems

I came across these problems : 1) Find the lowest natural number $k$ that satisfies the condition : $ 7 \mid A$ , where $A = 194^{19} + 125^{14} + k $ 2) Find the different prime numbers ...
4
votes
1answer
63 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 $$ ...
2
votes
2answers
381 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 ...
0
votes
1answer
32 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 ...
4
votes
2answers
45 views

Divide a square into different parts

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with geometry, which perhaps yields the shortest, simplest proofs, but other ...
-4
votes
0answers
20 views

Condensation of a number [on hold]

a)Let the first 2004 natural numbers be written 'at a stretch' to form a new number N.In other words, consider the number $$N = 12345678\ldots 200220032004$$ Find the number of digits of N.Let the ...
0
votes
0answers
31 views

Find number of element in $\{m\in\mathbb N:m\leq n\text{ and }m\text{ has the digit 3}\}$.

Inspired by a youtube video claiming that "almost all positive integer has the digit 3", I set myself a challenge: Give a formula, in terms of $n$, for the number of positive integer that is less ...
5
votes
3answers
418 views

Problem Solving Positive Integers

This is a very interesting word problem that I came across in an old textbook of mine. So I know the maximum value of the HCF has to be a factor of $540$ and mayhaps the Euclidean Algorithm, but other ...
5
votes
2answers
160 views

Prove that every integer $n\geq 7$ can be expressed as a sum of distinct primes.

My teacher said to use Bertrand's postulate and I have tried this for so long and I seem to go nowhere. Help would be appreciated. EDIT: Here's what I've done in my proof so far (I need help ...
4
votes
1answer
56 views

How to prove that any natural number $n \geq 34$ can be written as the sum of distinct triangular numbers?

Sloane's A053614 implies that $2, 5, 8, 12, 23$, and $33$ are the only natural numbers $n \geq 1$ which cannot be written as the sum of distinct triangular numbers (i.e., numbers of the form ...
6
votes
0answers
186 views

Does the set of $m \in Max(ord_n(k))$ for every $n$ without primitive roots contain a pair of primes $p_1+p_2=n$?

I have made the following observation: for those n even numbers that do not have primitive roots modulo n ,$Pr(n)$, the set $M(n)$ of those $k$ having a maximum multiplicative order $ord_n(k)$ ...
1
vote
2answers
137 views

How come $\ n\ $ always divides at least one of the item of the sequence?

Given positive integer$\ \displaystyle n,\ $ the sequence is: $\displaystyle 2^n$ $\displaystyle 2^n - 2^{n-1}$ $\displaystyle 2^n - 2^{n-1} + 2^{n-2}$ $\displaystyle 2^n - 2^{n-1} + 2^{n-2} - ...
0
votes
2answers
56 views

How many divisors of the combination of numbers?

Find the number of positive integers that are divisors of at least one of $A=10^{10}, B=15^7, C=18^{11}$ Instead of the PIE formula, I would like to use intuition. $10^{10}$ has $121$ divisors, ...
2
votes
3answers
69 views

Why would the cubic have $5$ roots?

The polynomial $P(x)$ is cubic. What is the largest value of $k$ for which the polynomials $Q_{1}(x) = x^{2}+(k-29)x-k$ and $Q_{2}(x) = 2x^{2}+(2k-43)x+k$ are both factors of $P(x)$? $P(x) = ...
3
votes
2answers
47 views

Find the least $N$ so there is no square

Find the least positive integer $N$ such that the set of $1000$ consecutive integers beginning with $1000 \cdot N$ contains no square of an integer. Let $x^2$ appear before $1000N$ so: $(x+1)^2 ...
-1
votes
0answers
65 views

How does constructing numbers in a set theoretic way help mathematics?

I recently read that the natural numbers can be constructed within the framework of the Zermelo-Fraenkel axioms via de axiom of infinity, where, with $n$ a natural number $n+1=n\bigcup \{n\}$ and ...
6
votes
2answers
732 views

Infinitely many primes of the form $8n+1$

I'm looking at this funny little problem involving proving the existence of an infinite number of primes of a certain form: Prove that there are infinitely many prime numbers expressible in the ...
6
votes
1answer
231 views

Proving $11! + 1$ is prime

Prove that: $$11! + 1$$ is a prime number. Without computing the number (or factorial). Obviously, from Wilson's theorem, a number $n$ is prime if, $$(n-1)! + 1 \equiv 0 \pmod{n}$$ Since $n = ...
12
votes
2answers
459 views

Show divisibility by 7

I was stuck at this question: Suppose $a^2+b^2=c^2$ for $a,b,c \in \mathbb Z$, and neither $a$ nor $b$ is a multiple of 7. Show that $a^2-b^2$ is a multiple of 7 I tried to write $b^2$ as ...
1
vote
1answer
38 views

How to use Principle of Inclusion-Exclusion here?

A while ago I posted a question: Coloring a Grid. Online, I seem to have stumbled upon a usage of PIE AOPS Wiki Solution AIME II #9. (1) Now, I have experience with PIE, but I do not see how to ...
1
vote
1answer
48 views

Probability of getting a five digit number divisible by 5 but with no two consecutive digits identical

A five digit number is written down at random. What is the probability of getting a number that is both divisible by 5 and doesn't have any 2 consecutive digits identical? I tried to analyse the ...
1
vote
2answers
40 views

To calculate the remainder of (111…) + (222…) + (333…) + (444…) + (555…) + (666…) +(777…) by 37

To Evaluate the remainder Question: $ (111...) + (222...) + (333...) + (444...) + (555...) + (666...) +(777...)$ mod $37$ In each bracket, the single digit $(1, 2, 3, ..., 7)$ is written $110$ ...
-2
votes
1answer
36 views

How would one solve the following equation: $(n-1)! +1 = nm$ [on hold]

Assume we do not know the Wilson's theorem, how would one solve this equation: $(n-1)! +1 = nm$ to show that there are infinite ...