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

learn more… | top users | synonyms (1)

2
votes
3answers
128 views

Number of ways to express a number as the sum of different integers

Given a number $n$, then $P_k(n)$ is the number of ways to express $n$ as the sum of $k$ integers. For example $P_2(6)=7$ $0+6=6$ $1+5=6$ $2+4=6$ $3+3=6$ $4+2=6$ $5+1=6$ $6+0=6$ Now I worked ...
0
votes
3answers
24 views

Show if $(a,p)=1$ and $x^2\equiv a\pmod{p^2}$ then $(x,p)=1$

Suppose $(a,p)=1$ and $x^2\equiv a\pmod{p^2}$ then $(x,p)=1$ How can I show that this is the case? If $(a,p)=1$ and $x^2\equiv a\pmod{p}$ then is also the case that $(x,p)=1$?
1
vote
1answer
31 views

Number of possible solutions in modular equation

I have given the result value $z$. I know that $$z \equiv x\cdot(x-1)\pmod p$$ where $p$ is prime and the value $p$ is fixed and given. I have also given the information, that $x \in \{m, M\}$, where ...
1
vote
3answers
39 views

Find a possible pair of numbers given HCF and a factor of the LCM

I was just going through a GCSE paper with a student and I came across a question that I'm struggling to find a good method for. The question was this: Martin thinks of two numbers. The ...
0
votes
0answers
30 views

Find all integer solutions to $x^2+y^2=5z^2$ [duplicate]

I'm having trouble with finding the integer solutions to $x^2+y^2=5z^2$. I'm guessing I have to show that $x=y=z=0$ is the only solution. Here's what I have tried... $x=y=z=0$ obviously a solution. ...
5
votes
3answers
68 views

Elementary proof that $-1$ is a square in $\mathbb{F}_p$ for $p = 1 \mod{4}$

I am trying to proof that $-1$ is a square in $\mathbb{F}_p$ for $p = 1 \mod{4}$. Of course, this is really easy if one uses the Legendre Symbol and Euler's criterion. However, I do not want to use ...
0
votes
1answer
57 views

What is wrong with this proof of a number theory competition problem?

Let $a$ and $b$ be positive integers. Suppose $a^n+n| b^n+n$ for any positive integer $n$, prove that $a=b$. My trial: Clearly $b\geq a$, write $b=a+d$, we must show that $d=0$. Now by assumption and ...
1
vote
2answers
62 views

Is there such an integer?

$\{a_n\}_{n=1}^{\infty}$ and $\{b_n\}_{n=1}^{\infty}$ are two infinite sequences of natural numbers such that for all $n$, $0\leq b_n<a_n$. Is it possible to exist an integer $k$ such that for all ...
5
votes
1answer
75 views

Prove $(8k)^{8k}+(8k+1)^{8k+1}$ and $(8k+1)^{8k+1}+(8k+2)^{8k+2}$ are never perfect squares

Prove $$(8k)^{8k}+(8k+1)^{8k+1}\ \ \text{ and } \ \ \ (8k+1)^{8k+1}+(8k+2)^{8k+2}$$ are never perfect squares ($k\ge 1$). mod $8$ gives $1$ for both, which is a quadratic residue, so doesn't ...
2
votes
2answers
41 views

Number Theory - Sum of Squares and Quadratic Residue

Show that if $p$ is a prime number satisfying $p\equiv 1\mod 4$, $a$ is an odd positive number, and there exists $b$ such that $a^2+b^2=p$, then $a$ is a quadratic residue $\mod p$. I know that ...
1
vote
2answers
26 views

Show $x^2+2x+1\equiv 27 \;\text{mod}\; 61$ is solvable and find the number of solutions.

I'll show how far I have got: $$x^2+2x+1\equiv 27 \;\text{mod}\; 61$$ $$(x+1)^2\equiv 27\; \text{mod} \; 61$$ So we need to find the Legendre symbol value for $$\begin{pmatrix} 27\\ 61 \end{pmatrix}$$ ...
3
votes
4answers
44 views

Find the following integer $ x $, s.t. $x \equiv 7^{57} \pmod {133}$

Find the following integers $x$: $x \equiv 7^{57} \mod 133$ I need to use fermat's little theorem for this problem which I know. It is for a prime number p. Then $a^{p-1} \equiv 1 \pmod p$ but I do ...
1
vote
2answers
22 views

When is $2$ a quadratic residue mod $p$?

For which prime numbers $p$, is $2$ a quadratic residue modulo $p$. I know that $2$ is a quadratic reside iff $$2^{\frac{p-1}{2}} =1 \; \bmod \;(p) $$ so $$2^{p-1} =1 \; \mod \; (p). $$ But I ...
4
votes
2answers
34 views

Let $n$ be an integer. If $(a,m)=1$, there exists an integer $a'$ such that $a'\equiv a \pmod{m}$ and $(a',n)=1$.

Let $n$ be an integer. If $(a,m)=1$, there exists an integer $a'$ such that $a'\equiv a \pmod{m}$ and $(a',n)=1$. I am not sure if the above statement is true. It has been annoyingly elusive to ...
0
votes
2answers
16 views

A question in Number Theory about Euler Theorem/Fermat little theorem

I tried to solve this question but without a success. for every prime number $$p\ge7 $$ and every $$n \in \mathbb N$$ : $$10^{n(p-1)}\equiv 1 (\text{mod }9p) $$ I tried to use Euler theorem. but It ...
1
vote
1answer
63 views

The following is a necessary condition for a number to be prime, from its digit expansion. Has it been referred somewhere?

Concerning a numbers’ digits we know some necessary conditions on them for the number to be prime, besides the last digit having to be odd (except for prime 2). For example in decimal representation ...
2
votes
4answers
27 views

Prove that if $p\ge 7$ then $\exists n\in\Bbb{Z}$ such that $10^{n(p-1)}\equiv1 \mod 9p$.

Prove that if $p\ge 7$ then $\exists n\in\Bbb{Z}$ such that $10^{n(p-1)}\equiv1 \mod 9p$. Edit: $p$ is prime, of course. I tried using theorems regarding Euler, but I can't seem to arrive at something ...
0
votes
1answer
52 views

If you know $N=a^2+b^2$ how to compute $a$ and $b$ for large $N$?

Having tested that $N$ is such that every exponent of a prime in the prime factorisation of $N$ congruent to $3 \bmod 4$ is even. Then for large $N$ can we find $a$ and $b$, such that ...
6
votes
1answer
231 views

Increasing sequence of divisors of a quadratic trinomial

This question is from a Russian contest, the 2011 Tuymaada Olympiad. It's the fourth question on day two for the problems at grade level 2. Let $P(n)$ be a quadratic trinomial with integer ...
1
vote
2answers
28 views

if d divides n then prove that fibonacci of d divides fibonacci of n

prove that if $d$ divides $n$ then prove that fibonacci of $d$ divides fibonacci of $n$. i have tried to write $F(n)$ as a multiple of $F(d)$ using the fact that $n = ad$ for some natural $a$ but got ...
3
votes
3answers
90 views

For a prime $p\ge 17$ is $\dfrac{p^2-1}{24}$ ever a prime?

It was indicated in the comments of this MO question that if $p\ge5$ is a prime then $24|p^2-1$. Indeed $p=6k\pm1$ and $p^2-1=36k^2\pm12k+1-1=12k(3k\pm1)$ and exactly one of $k$ and $3k\pm1$ is even. ...
4
votes
3answers
428 views

Prove that the integers $x$, $x+6$, $x+12$, $x+18$, $x+24$ can only be prime if $x$ is $5$.

Prove that the integers $x$, $x+6$, $x+12$, $x+18$, $x+24$ can only be prime if $x$ is $5$. I am very new to proofs and not completely sure of how to approach this one. I tried several different ...
-6
votes
3answers
63 views

Solve the equation $2xy+2x-5y=40$, if $x$and $y$ are whole numbers. [closed]

Solve the equation $2xy+2x-5y=40$, if $x$ and $y$ are whole numbers. Could anyone give me a step by step answer?
4
votes
2answers
66 views

Find all values of $x,y,z$ positive integers such that $4^x+4^y+4^z$ is a perfect square

I have to solve the equation $$4^x+4^y+4^z=k^2$$ I posted my solution but i don't know if there are other solution. How can i demonstrate that this expression is a perfect square? Are there oter ...
1
vote
0answers
37 views

Show this indivisibility

I have to learn for an exam but I can't solve this problem. Let $s_1, \cdots, s_n$ be positive integers, $n> 1.$ $t$ is a multiple of the product $\displaystyle \prod_{i = 1}^{n}{s_i}$. Prove ...
0
votes
1answer
74 views

equation $x^4 + y^4 = z^4$

Diophantine equations that are insoluble in $\mathbb{Z}$ may become soluble in finite integral domains. Show that \begin{equation*} x^4 + y^4 = z^4 \end{equation*} is soluble (as a congruence) in ...
0
votes
0answers
34 views

First whole number solution for linear equation

I have a simple linear equation with 2 variables(both whole numbers) $$\left ( 840x + 3 \right )= 9y$$ I need to find the minimum value of x for which this equation holds. Just by looking at the ...
0
votes
1answer
44 views

question on two-square problem.

Let $A_1, A_2$ be two quadratic residues of ($4k + 3$)-prime $p$ that satifsy $0 < A_1 < A_2 < p$. Prove that $A_1 + A_2 \equiv 0 \pmod p$ is impossible. Illustrate this result with $p = ...
3
votes
3answers
37 views

When $p=3 \pmod 4$, show that $a^{(p+1)/4} \pmod p$ is a square root of $a$

Let $a$ and $p$ be integers such that $p$ is prime, and $a$ is a square modulo $p$. When $p\equiv3\pmod4$, show that $a^{(p+1)/4}\pmod p$ is a square root of $a$. Why does this technique not work when ...
1
vote
1answer
44 views

Find the smallest integer that is divisible by exactly $X$ perfect squares.

Is there a method to find the smallest integer divisible by exactly $X$ perfect squares? Example: find the smallest positive integer divisible by exactly 2015 perfect squares. I've been trying to ...
0
votes
1answer
24 views

Proving $S_1 \subseteq S_2$ for transitive closure

This is one of the problem I have been working from Velleman's How to prove book: Suppose $R_1$ and $R_2$ are relations on $A$ and $R_1 \subset R_2$l (a) Let $S_1$ and $S_2$ be the reflexive ...
3
votes
1answer
45 views

Could all iterates of $s(n)=2n+1$ be composite for some starting $n$?

Let $s(n)=2n+1$ and $\sigma(n)=\{n,s(n),s^2(n),s^3(n),\ldots\}$, where $s^3$ denotes functions composition, $s^3(n)=s(s(s(n)))$. For example $\sigma(11)=\{11,23,47,95,\ldots\}$. As another example ...
2
votes
1answer
51 views

how to prove by induction the $ (1+x)^{n}>1+nx+nx^2$

Prove by induction the formula $ (1+x)^{n}>1+nx+nx^2$ for $x>0$ real number and $n\ge 3$ my try : multiply both sides by $(1+x)$ gives $ (1+x)^{n+1}>1+(n+1)x+(2n+nx)x^2$ have I done ...
0
votes
1answer
35 views

Show the following statement

Let $S_a$ the product of the first a primes. If $s_a (n)= \sum \limits_{d|(n,S_a)} \mu(d)$ = 1 , if n has no prime factors < a and $0$ otherwise. Then it should be showed $\sum \limits_{n \le b} ...
0
votes
3answers
44 views

Negative number to the power of…

We know that negative number to the power of any integers or some fractions will always have a solution. Is it possible for us to solve $(-2)^\frac 13$ or $(-2)^e$, by modifying/extending our ...
2
votes
0answers
40 views

Prove that the highest power of $n$ contained in $(n^r-1)!$ is $\frac{n^r-nr+r-1}{n-1}$.

Prove that the highest power of $n$ contained in $(n^r-1)!$ is $\frac{n^r-nr+r-1}{n-1}$. Attempt: I want to use the following theorem: The largest exponent of $e$ of a prime $p$ such ...
3
votes
2answers
72 views

Backwards proof of Fermat's Little Theorem

$$\textrm{Let }p \in \mathbb{N}. \textrm{ Show that }\forall n \in \left \{ 1,2,...,p-1 \right \} \textrm{if } n^{p-1} \equiv 1 \mod p \Rightarrow p \in \mathbb{P}$$ This is basically Fermat's ...
3
votes
4answers
67 views

Prove that number of zeros at the right end of the integer $(5^{25}-1)!$ is $\frac{5^{25}-101}{4}.$

Prove that number of zeros at the right end of the integer $(5^{25}-1)!$ is $\frac{5^{25}-101}{4}.$ Attempt: I want to use the following theorem: The largest exponent of $e$ of a prime $p$ ...
1
vote
1answer
39 views

how to solve system of quadratic equations (mod N)

Given a two equations: $${(ax_1 + b)}^2 = c_1 \pmod N$$ $${(ax_2 + b)}^2 = c_2 \pmod N$$ $N=p.q$ $p$ and $q$ are large primes $x_1, x_2$ and $c_1, c_2$ are known Is it computationally feasible to ...
0
votes
0answers
6 views

Unique symmetric multilinear form associated to a form

Let $F(\mathbf{x}) \in \mathbb{Z}[x_1, ..., x_n]$ be a form of degree $d$. In an article I am reading, it says to associate to $F$ the unique symmetric multilinear form $F(\mathbf{x}_1| ... | ...
10
votes
3answers
88 views

Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$.

So the problem states: Show that for every prime $p$, there is an integer $n$ such that $2^{n}+3^{n}+6^{n}-1$ is divisible by $p$. I was thinking about trying to prove this using the corollary to ...
2
votes
0answers
41 views

Diophantine eqution with odd prime

HOW to find all possible set of solutions of an equation type $y^p \pm 2 = x^2$, where $p$ is any odd prime High regards to one and all
3
votes
1answer
68 views

Distribution of composite numbers

This question is moved from mathoverflow, there are several excellent answers at mathoverflow which improve my question greatly. For more information, please see the original question posted on ...
-1
votes
3answers
85 views

Prove that $\sqrt{2n}$ is irrational if $n$ is an odd natural number. [closed]

We know that $\sqrt{2}$ is irrational, but how would we go about proving this? I have already attempted to follow the same method of proving this as in the proof of $\sqrt2$ , but I cannot end up ...
3
votes
2answers
52 views

Prove that if $a \mid n$ then $a^2\mid (n + 1)(n − 1) + 1$

I have this review question for an exam and I was hoping someone can help me solve it: Prove that if $a \mid n$ then $a^2\mid (n + 1)(n − 1) + 1$ this is what I have so far, not sure if it is ...
1
vote
0answers
60 views

Determine all natural numbers n and m that satisfying in this equation. [closed]

I'm trying to solve the following question: Determine all natural numbers n and m such that: $$n ^ { n ^ n } = m^m.$$ I don't have any idea about this question. Can somebody help me or give ...
0
votes
2answers
21 views

If $C|a$ and $C|b$ then $C|(ax+by)$

If $c|a$ and $c|b$ then $c|(ax+by)$ where $c,a,b$ are integers Proof: Suppose $c|a$ and $c|b$ then we can represent as the following: $a=cx$ where $x$ is an integer $b=cy$ where $y$ is an integer ...
2
votes
2answers
60 views
2
votes
1answer
29 views

What is the sum of the quadratic residues of prime $p=4k + 3$?

If prime $p=4k + 1$ we know that if a is a quadratic residue then $-a$ is a quadratic residue, So there are $(p - 1)/4$ pairs of integers whose sum is $p$. So the sum over all quadratic residues is ...
1
vote
4answers
73 views

Let $a,b$ be relative integers such that $2a+3b$ is divisible by $11$. Prove that $a^2-5b^2$ is also divisible by $11$.

The divisibility for $11$ of $a^2 - 5b^2$ can be easily verified; in fact: $$a \equiv \frac {-3}{2}b \pmod {11}$$ therefore $$\frac {9}{4}\cdot b^2 - 5b^2 = 11(-\frac{b^2}{4}) \equiv 0 \pmod {11}.$$ ...