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

learn more… | top users | synonyms

0
votes
0answers
46 views

What is the efficient way to compute ${n \choose r} \mod k$?

We know that $n\choose r $ = $\frac {n-r+1}{r}$$ n\choose r-1$ And we also know that $(a * b) \mod k = ((a\mod k) *(b\mod k)) \mod k$ Fermat's Little theorem $a^{\phi(m)-1} = a^{-1} \mod m$ ...
2
votes
2answers
77 views

Integer root of a quadratic [closed]

Determine the sum of all (distinct) positive integers $ n$ , such that for some integer $a$, $$ n^2 -an + 6a = 0. $$
-3
votes
2answers
58 views

Smallest natural number $x$ that is twice a perfect square, three times a perfect cube, and five times a perfect fifth power [closed]

I am trying to find the smallest positive integer $x$ such that there are some other positive integers $a,b,c$ with \begin{align*} \frac{x}2&=a^2 \\ \frac{x}3&=b^3 \\ \frac{x}5&=c^5 ...
1
vote
3answers
79 views

If $p \mid a^n$ then does $p^n \mid a^n$? [duplicate]

I'm trying to figure out if the statement is true or not and I need to prove it if so. Let $p$ be a prime and $a$ be an integer. If $p\mid a^n$ , is it true that $p^n\mid a^n$ ? I'm not sure how i ...
8
votes
4answers
567 views

What are some elementary results (number theory) using theorems that went long-unproven?

Firstly, I do not mind if there are examples from fields other than number theory! This was just the first field, and where I think the richest examples, may come from. Now to elaborate on the title, ...
2
votes
4answers
118 views

Let $a$, $b$, and $c$ be integers satisfying $a^2 + b^2 = c^2$. Prove: $abc$ must be even.

I'm pretty sure that this can be proved by reductio ad absurdum, and have a proof for that. However, I'm not sure how to prove this using any other method of proof. It's my first time taking a course ...
0
votes
2answers
41 views

For fixed $n, c \in \mathbb{N}$ find all natural number pairs $(a,b)$ to $a +nb = c$

I arrived at this problem as I am trying to find a discrete probability distribution of trying to catch a frog hopping on a number line using a particular method of counting [When the frog initial ...
0
votes
1answer
33 views

Another Division Algorithm Question.

Show that if a,b,c are integers, with b > 0 and c >0, such that when a is divided by b, the quotient is q and the remainder is r, and when q is divided by c, the quotient is t and the remainder is s, ...
2
votes
3answers
90 views

For what prime numbers $p$ is $x^2+x+1$ irreducible in $\mathbb{F}_p[X]$

I think it's enough to search for the prime numbers where $x^2+x+1=0$ is not solvable, but I am not sure where to start. Thank you
1
vote
1answer
44 views

Is there any $k$ such that there are no primes with $k$ digits?

It seems that for any base $b\geq 2$, and for any number of digits $k\geq 2$, there is always some prime number that is $k$ digits long in base $b$. For example, in base $10$, for $2\leq k\leq 10$ we ...
1
vote
1answer
41 views

Divisibility Question.

Show that if $a$ and $b$ are odd positive integers, and $b$ does not divide $a$, then there are integers $s$ and $t$ such that $ a = bs + t$ where $t$ is odd and $|t| <b$. Let a = 2k +1 and b = 2j ...
2
votes
3answers
116 views

How to calculate the sum of digits of $2^n$?

How do I find the sum of digits of $2^n$ in general? Sum of digits of $2^1=2$ is $2$. Sum of digits of $2^{10}=1024$ is $7$. I have check there is no obvious pattern or any recurrence that i can ...
2
votes
3answers
50 views

Prove that $[ab]=[[a][b]]$

Let $a,b,N\in\mathbb{Z}$, where $N>0$. Prove that $[ab]=[[a][b]]$, where $[x]$ denotes the remainder of $x$ after division by $N$. Here's my attempt: Proof. Since $x\equiv{[x]}_c\pmod c$, we ...
0
votes
2answers
35 views

Find all primes different from three for which $(3|p)=1$

Find all primes different from three for which $(3|p)=1$, where $(3|p)$ denotes the Ligendre symbol.
2
votes
2answers
52 views

Positive integers $n$ which can be written as $x^2-3y^2$

My problem is: Which positive integer $n$ can be expressed in the form $x^2-3y^2$? First I consider the equation $$x^2-3y^2=p$$ with $p>2$ is a prime. By quadritic residue, notice that ...
1
vote
0answers
47 views

Can we choose $p$ integers within $2p-1$ arbitrary integers, such that the sum of them is divisible by $p$?

Suppose we have $2p-1$ integers(not necessarily distinct), where $p$ is a prime. Can we always find $p$ integers within it such that the sum of them is divisible by $p$? this can be verified when $p$ ...
0
votes
1answer
33 views

If we assume that their is a prime between n and 2n…

If we assume that their is a prime between 'n' and '2n' then, how to prove that any integer greater than 1 can be written as sum of two primes?(In this we treat 1 as a prime)
0
votes
4answers
104 views

Is there an intuitive explanation for $ x^2+y^2=7 z^2 $ doesn't have any integer solution?

As we all know that $x^2+y^2=z^2$ has infinite integer solutions. Can we use this fact to give an intuitive explanation for $ x^2+y^2=7 z^2 $ doesn't have any integer solution? $x, y, z $ are positive ...
1
vote
3answers
179 views

How to find the LCM of three numbers?

We know that LCM(a,b)= [ab/GCD(a,b)]. What about LCM (a,b,c)? Can anyone help us because our instructors doesn't know the ways and she just lay the problem on us. Thanks.
15
votes
5answers
3k views

Is it true that the Fibonacci sequence has the remainders when divided by 3 repeating?

About this Fibonacci sequence, is it true that the remainders when divided by three repeat along with the sequence like this: Fibonacci sequence: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
10
votes
3answers
620 views

Find the highest power of two in the expression.

What would be the highest power of two in the given expression? $32!+33!+34!+35!+...+87!+88!+89!+90!\ ?$ I know there are 59 terms involved. I also know the powers of two in each term. I found that ...
2
votes
1answer
106 views

Sum of consecutive numbers

I was wondering if there a way to figure out the number of ways to express an integer by adding up consecutive natural numbers. For example for $N=3$ there is one way to express it $1+2 = 3$ I have ...
2
votes
2answers
19 views

How to find the numbers of Bezout identity for two numbers

I'm having troubles finding two numbers a,b such that $ 288a+177b=3=gcd(177,288) (1) $ I've been writing the equations of the Euclids algorithm one over another many times to get any pair that verify ...
3
votes
2answers
39 views

BMO preparatory question

Q) Let $3\leq n$ be an odd integer and let $a_1,a_2,...a_n$ be fixed positive integers. For each of the $n!$ permutations $\pi=(\pi_1,\pi_2,...,\pi_n)$ of $(1,2,...,n)$, define $$f(\pi) = a_1\pi_1 + ...
0
votes
2answers
63 views

How to prove that every number, such that it's square root is integer, has odd number of divisors?

How to prove that every number, such that it's square root is integer, has odd number of divisors, Is it same as saying every number, such has odd number of divisors is perfect square?
1
vote
1answer
44 views

Can someone help me predict a few numbers that follow the pattern in these numbers?

I have these numbers: 9149 5915 9199 7147 6156 7917 There obviously is some sort of pattern between them in that the first and the last digits are the same, and the second and third digits ...
2
votes
3answers
59 views

Integer $2 \times 2$ matrices such that $A^n = I$

An earlier question today motivates this slight variant: For what natural numbers $n$ does there exist a non-identity integer $2\times 2$ matrix $A$, such that $A^n = I$? (And let's say $A^k \ne I$ ...
3
votes
1answer
75 views

Proving that $1+2^m+3^m+…n^m$ is divisible by $(n+1)$

Proving that $$1+2^m+3^m+...n^m$$ is divisible by $$(n+1)$$ where $n$=Integer even number $m=$positive integer number, so that $m\neq n,2n,3n...$
7
votes
3answers
118 views

suppose that $n$ is natural number and even, show that $n \nmid 1^n +2^n+3^n + \ldots (n-1)^n$.

suppose that $n$ is natural number and even, show that $n \nmid 1^n +2^n+3^n + \ldots (n-1)^n$. so I put $n=2k$ and I supposed $n \mid 1^n +2^n+3^n + \ldots (n-1)^n$ then with a little calculation we ...
3
votes
2answers
53 views

Hint for Number Theory problem from Engel.

I am trying to solve : Given: $n>3$ prove that $2^n+1$ is not a power of $3$. I just need a hint for this problem.I am trying to solve by thinking about divisibility and congruences but can't ...
0
votes
3answers
37 views

An elementary property of repunits

For the repunits $R_n$, where $R_n={(10^n-1)}/{9}$, verify the assertion. If $\gcd(n,m)=1$, then $\gcd(R_n,R_m)=1$. I've been trying to solve this problem, however, every attempt so far has been ...
1
vote
0answers
13 views

Vandermonde determinants quotient [duplicate]

I have to prove that for any integers $k_1<k_2<...<k_n$ the quotient: $$ \frac{V_n (k_1,k_2, ..., k_n)}{V_n (1, 2, ..., n)} $$ is an integer, where: $$ V_n (k_1,k_2, ..., k_n) = \prod_{1 ...
0
votes
1answer
42 views

To find all positive integers $n$ such that $a\in \mathbb Z ; n|a(a-1) \implies n|a $ , or $n|a-1$

How do we find all positive integers $n$ such that $a\in \mathbb Z ; n|a(a-1) \implies n|a $ , or $n|a-1$ ? The primes certainly satisfy this condition ; what other integers do satisfy this condition ...
4
votes
0answers
40 views

Integers in the form $\sum_{j=0}^n a_j2^j3^{n-j}$

Let $n>0$ be an integer. Let also $a_j$ be some integer in the set $\{0,1,\ldots,\binom{n}{j}\}$ for all $j=0,1,\ldots,n$. Then, how many integers can be written in the form $$2^n ...
3
votes
1answer
127 views

Prove $1! + 2! + 3! + \ldots + n! =y^3$ has only one solution in the set of natural numbers?

I actually know that the above equation is true for $n=1$ and $y=1$ but am unable to prove it for the entire set of natural numbers. Can anyone please help me solve this in a simple way?
5
votes
0answers
79 views

number at the circumference

Determine all natural numbers $n$ such that the numbers $1,2,3, . . . ,n$ can be placed on the circumference of a circle, such that for any natural number $s$ with $1 \le s \le \frac{n(n+1)}{2}$ there ...
4
votes
1answer
86 views

Distribution of Rational Numbers on $[0,1]$

If I define the function $$\Phi(n) := \sum_{k=1}^n \phi(k),$$ where $\phi$ is Euler's totient function, and I define $Q_n(x)$ to be the number of distinct rational numbers with demoninators $\leq ...
0
votes
0answers
27 views

Looking for an English translation of Descartes's mathematical works

Good day to everyone! I am looking for an English translation of Descartes' mathematical works (particularly in elementary number theory). Would someone be kind enough as to point me to an ...
2
votes
1answer
53 views

Insight into Abel's impossibility theorem

Let 's consider the polynomial of degree $7$:$$f(x)=x^7-28x^6+ 322x^5-1960x^4+6769x^3-13132x^2+13068x-5040 $$ I am trying to get some insights into Abel's impossibility theorem. Does this theorem ...
4
votes
1answer
90 views

Finding appropriate m,n

I came across the following question in a book(with no solutions) that I have been solving:- Prove that for any positive integers $x$ and $y$, $x\not =y$, one can find positive integers $m$ and $n$ ...
3
votes
3answers
94 views

Prove that there exists infinitely many pairs of relatively prime integers $(a,b)$.

Prove that there exists infinitely many pairs of relatively prime integers $(a,b)$ such that both the quadratic equations $$x^2+ax+b=0$$ $$ x^2+2ax+b=0$$ has integer roots. I tried the ...
1
vote
7answers
105 views

Give a direct proof of the fact that $a^2-5a+6$ is even for any $a \in \mathbb Z$

Give a direct proof of the fact that $a^2-5a+6$ is even for any $a \in \mathbb Z.$ I know this is true because any even number that is squared will be even, is it also true than any even number ...
3
votes
1answer
59 views

How many positive integers less than 1000 are multiples of 5 and are equal to 3 times an even number?

Question: How many positive integers less than 1000 are multiples of 5 and are equal to 3 times an even number? So Multiples of $5$ and $6$ If a number is a multiple of $5$ and $6$ then it is a ...
3
votes
1answer
48 views

Find a function $M$ such that $M(x)=1 \forall x\neq 0$ and $M(0)=0$

Find a function $F$ from $S*S$ to $\{0,1\}$ where $S$ is the set of first $12$ positive integers such that : $$F(a,b) = \begin{cases}0 &, \text{for $b \ge a$}\\ 1 & \text{otherwise }. ...
0
votes
4answers
207 views

Let $w, x, y, z$ be natural numbers. Find the correct alternative.

Let $w$, $x$, $y$, $z$ be four natural numbers such that their sum is $8\cdot m+10$, where $m$ is a natural number. Given $m$ which of the following is possible: The max. possible value of ...
3
votes
1answer
40 views

Fibonacci Numbers $F_n$ and $F_{n + 1}$ are relatively prime for all $n \geq 0$.

I have looked a bunch of solutions of this problem on the web. But I want to know that whether my solution is correct or not. My solution is as follows Proof(By Induction) $P(n)$:The Fibonacci ...
3
votes
4answers
99 views

$2^{2^n}+5^{2^n}+7^{2^n}$ is always divisible by $39$

This problem is really bothering me for some time, I appreciate if you have some idea and insight. Prove that $$2^{2^n}+5^{2^n}+7^{2^n}$$ is divisible by $39$ for all natural numbers ...
7
votes
2answers
114 views

At least 99% of these numbers are composite

This is from a contest preparation: Prove that at least 99% of these numbers $$10^1+1,10^2+1, 10^3+1, ..., 10^{2010}+1$$ are composite. The problem is from 2010, obviously. I was ...
7
votes
1answer
186 views

Sum of a Sequence of Prime Powers is a Perfect Square

Find all primes p such that $p^{2n}+p^{2n-1}+p^{2n-2}+\cdots+p^{2}+p+1$ is a square for some value of n.
2
votes
1answer
48 views

Improving the inequality $x\sigma_1(x) \leq \sigma_1(x^2)$ for $x \in \mathbb{N}$

Let $\mathbb{N}$ be the set of positive integers. For $x \in \mathbb{N}$, $\sigma_1(x)$ gives the sum of the divisors of $x$. (For example, $\sigma_1(3) = 1 + 3 = 4$.) We call the ratio $I(x) = ...