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

learn more… | top users | synonyms

2
votes
2answers
91 views

$2^{8420} - 9$ is prime or not

How to prove $2^{8420} - 9$ is or isn't a prime number? I tried modding it by 10 to get the last digit, but that's a 7 which doesn't help. We've only been covering successive squaring in this ...
2
votes
1answer
28 views

The modular n-th root (mod p*q)

I am interested in the solution of the following modular equation. Is the solution unique? If not, how difficult do find more than one solutions? $$x^n \equiv a \; \bmod (p\cdot q)$$ where $p$ and ...
1
vote
1answer
40 views

$\sqrt {-6}$ is not prime in $\mathbb{Z}+\mathbb{Z}\sqrt {-6}$

Suppose $\sqrt{-6}|(a+b\sqrt{-6})(c+d\sqrt{-6})$. I need to show that $\sqrt{-6}$ does not divide $(a+b\sqrt{-6})$ and does not divide $(c+d\sqrt{-6})$. I thought you might arrive at some ...
0
votes
4answers
29 views

Let $p \geq 5$ and prime. Show $p^2 + 2$ is divisible by three.

I know I have to use the division algorithm to put into the form $p^2 + 2 = 3q + r$ but everything I've tried after that has lead me to a dead end. I've mainly been trying to show $r=0$ or to make the ...
0
votes
1answer
35 views

Concatenating squares - is this solution unique?

This question asks about concatenated squares to make a square number. For example $[4][9]=49, [16][9]=169, [3136][441]=3136441, [64][009]=64009$ I've been doing a bit of investigating for the case ...
1
vote
1answer
30 views

Best self study book with answers to selected questions for analytic number theory?

All: Can anyone recommend Best self study book with answers to selected questions for analytic number theory ? If a book have no answers to questions, but if you know if some professors choose the ...
2
votes
2answers
31 views

Prove that if $\gcd(a,b)=1$ then $\gcd(a^m, b)=1$

I am using the Euclidean Algorithm (EA) for proof. Let $a>b$ and by EA we have $$ \begin{align} a=q_0 b+r_1 & & & \text{where }0\leq r_{1}<b \\ b=q_1 r_1+r_2 & & & ...
1
vote
0answers
23 views

looking for origin of number theory problem on 4x-floor-sqrt (maybe IMO)?

this problem was recently posed by BS in the number theory chat room. he thinks it may originate from the International Math Olympiad & he says he has a solution. has anyone seen it there? looking ...
1
vote
0answers
20 views

Prove that this sequence of fractions is returned unchanged after the divisor recurrence, the matrix inverse, and the sum over divisors.

Consider the fraction of binomial coefficients and powers of $4$: $$a(n)=\frac{\binom{2 (n-1)}{n-1}}{4^{n-1}}$$ starting: ...
0
votes
3answers
35 views

Modular calculus and square

I want to prove that $4m^2+1$ and $4m^2+5m+4$ are coprimes and also $4m^2+1$ and $4k^2+1$ when $k\neq{m}$ and $4m^2+5m+4$ and $4k^2+5k+4$ when $k\neq{m}$. Firstly : Let $d|4m^2+1$ and $d|4m^2+5m+4$ ...
2
votes
2answers
71 views

Prevent similar consecutive colours for a pie chart

Background Calculating colours for pie chart wedges. Consider: $$ \begin{align} d(n)&=\frac{\theta}{t}\times n\\ \end{align} $$ Where: $\theta$ is the degrees in a circle (360) $t$ is the ...
13
votes
6answers
977 views

Is there any book/resource which explain the general idea of the proof of Fermat's last theorem?

I look for a book/resource which display the general idea of the proof of Fermat last theorem in a simple manner for the public. I mean, books which is not for mathematicians but for the general ...
1
vote
2answers
47 views

what does the phrase “no zero divisors mod 13” mean?

I came across this while trying to work a problem : What is a "zero divisor" and how are they able to use zero product property as if it is an algebraic equation ? Highly appreciate any help ! ...
0
votes
2answers
25 views

replacing numbers to get final anser

I found this question in a random problem solving book that I was reading and wanted to know how you would solve it. I am not sure as how to go about this. Take any positive integer $n$ with fewer ...
1
vote
1answer
43 views

Find all the triples $(x,y,z)$ such that $ax+by=cz$

Let $a,b,c,x,y,z >1$ if $\gcd(a,b,c)=1$, find all the non-trivial triples of positive integers $(x,y,z)$ such that $ax+by=cz$. Progress I have been struggling finding the solutions. At first, I ...
1
vote
0answers
38 views

Which numbers have the sum of their digits equal to the sum of the digits of their inverse?

$n$ is a number such as $n \in \mathbb{N}$ and $n >0$.(Eg. $n = 8$) $p$ is the sum of the digits of $n$ in base $10$.(Eg. $n=80$, $a = 8+0 = 8$) $q$ is the sum of the digits of $1/n$ in base ...
0
votes
1answer
33 views

Number of integer lattice points within a circle

I am trying to solve a problem on codeforces, to be precised, this problem. I was able to figure out that the solution is $N(n) - N(n-1)$ where $N(n)$ is the number of lattice points withing a circle ...
2
votes
1answer
49 views

Number theory problem from 11th Iberoamerican olympiads

Given a number $n \in \mathbb{N}$, such that $n>1$, let us consider all the fractions of the form $1 \over{ab}$, where $a$ and $b$ are coprime natural numbers such that $0<a<b \leq n$ and ...
3
votes
4answers
52 views

Are all those numbers coprime?

The values of $4m^2+1$ and $4m^2+4m+5$ for $m\geq{1}$ are (resp.) 5,17,37,... and 13,29,53,... Those numbers seem to be all coprime : how to prove it if it is true, please ?
-1
votes
1answer
92 views

Cut squares from sheet

A rectangular paper sheet of M*N is to be cut down into squares. ...
0
votes
2answers
33 views

finding values of $x$ in $Z$

Find all values of $x$ such that $\frac{x-4}{2x-3}\in\mathbb Z$? I came up with this question to see if it could be solved based on some other questions I did myself. I thought this could not be ...
2
votes
1answer
40 views

How to solve $n$ in $5^{n-1}\equiv 1 \pmod{n}$

$5^{n-1}\equiv 1 \pmod{n}$ I see that this holds true when $n$ is prime by Fermat's little theorem. However there could be few composite numbers, $n$ for which the congruence might hold true ? How to ...
1
vote
0answers
21 views

Find the reflection point $P$

On the real number line, paint red all points that correspond to points of the form $81x+100y$, where $x$ and $y$ are positive integers. Paint the remaining integer points blue. Find a point $P$ on ...
3
votes
1answer
79 views
+100

How to represent Fermat number $F_n$ as a sum of three squares?

Let $F_n=2^{2^n}+1$ be the Fermat number. How to represent the Fermat number $F_n$ for $n \geq 3$ as a sum of three squares of different natural numbers? For example for $n=3$ we have $$ ...
3
votes
1answer
27 views

If $x \equiv a \pmod {p_1}$ and $x\equiv a \pmod{p_2}$, then is it true that $x\equiv a \pmod{p_1p_2} ?$

$p_1, p_2$ are distinct prime numbers I have just observed this pattern when solving this problem. Is there a simple way to prove/disprove it ?
0
votes
3answers
43 views

Congruences in number theory

I am working on a worksheet on number theory and I have to solve the following congruences: $$7^{128}=n\mod 13$$ Find $n$. And $$28x^2=1\mod37$$ How should I solve these congruences? I have no clue ...
1
vote
2answers
59 views

Find the remainder when $2^{561}$ is divided by $561$ using simple congruence properties.

$2^{561}\equiv ? \pmod{561}$ Few observations : $561 = 3\times 11\times 17$ So Fermat's little theorem is not useful here. Any hints ? If possible, kindly avoid carmichael numbers/group theory/euler ...
1
vote
7answers
80 views

Prove by induction that $n(n+1)(n+5)$ is multiple of 3

$$n(n+1)(n+5) = 3d$$ I cannot figure out how to solve this homework question. A friend gave me a solution I couldn't make sense of, and I hope there's something easier out there. Also, what would be ...
0
votes
0answers
21 views

Modular nth roots, e.g. $x^5 \equiv 6 \pmod{31}$

I want to algorithmically solve the (large integer) modular root equation $$x^n \equiv a \pmod {p^k},$$ assuming for simplicity that $p$ is prime, $\gcd(a,p)=1\;$ and $n$ odd. If $q \equiv n^{-1} ...
0
votes
0answers
44 views

Proving that $3 = 9^{-1} \pmod{26}$

Prove that $3$ is the multiplicative inverse of $9 \pmod {26}$ $$\quad26\quad1\quad0\\2\quad9\quad0\quad1\\\;\;1\quad8\quad1\quad{-2}\\\quad\;1\quad-1\quad3$$ Hence $3$ is the multiplicative inverse ...
1
vote
1answer
9 views

If $n \in \mathbb{N} - \{1\}$, $ a \in \mathbb{Z}$, and $gcd(a,n)=1$, show there is $1 \leq i<n$ with $n|(a^i -1)$.

If $n \in \mathbb{N} - \{1\}$, $ a \in \mathbb{Z}$, and $gcd(a,n)=1$, show there is $1 \leq i<n$ with $n|(a^i -1)$. So far I have shown that, if $gcd(a,n)=1$, then $gcd(a^j,n)=1$. I also have a ...
0
votes
0answers
18 views

Quickie on NT notation

Is there a notation for the set of quadratic residues of an arbitrary natural $n$? I can't seem to find it anywhere on the internet, and it would be very nice if I could use this instead of every time ...
7
votes
3answers
451 views

How many ways are there to write $675$ as a difference of two squares?

How many ways are there to write the number $675$ as a difference of two squares? Is there a way to generalize this?
2
votes
2answers
48 views

Simple proof that $a$ is coprime

Prove that if $a$ divides $x^n-1$ and $x^m-1$, then $a$ is coprime with $x$. I think this should be easy but I can't think of a way to do it.
6
votes
2answers
102 views

$\gcd(a,b)$ compared to $\gcd(3a,b)$

$\gcd(a,b)=\gcd(3a,b)$? They are obviously not equal in general, as $\gcd(ax, bx)=|x|\gcd(a,b)$.
1
vote
2answers
51 views

Lucas Numbers Proof $L_n = \alpha^n + \beta^n$

Proof by Induction: Lucas numbers are recursively defined as: $L_n = L_{n-1} + L_{n-2}$ where $L_1 = 1$ and $ L_2 = 3 $for $n \ge 3$ Show that: $L_n = \alpha^n + \beta^n$ for $\alpha = ...
2
votes
0answers
10 views

$ab$ is a quadratic residue modulo $c$, and $-ab$ is a QR modulo $c^{(p-1)/2}$

Given three nonzero integers, $a,b,c$. If $ab$ is a quadratic residue modulo $c$ and $-ab$ is a quadratic residue modulo $c^{(p-1)/2}$ for a fixed odd prime $p$, what can be said about $a,b,c,$ or ...
2
votes
1answer
51 views

Show that the equality is true

If $f$ is a Completely multiplicative function and $g$ is an arithmetic function such as $g(1) \neq 0$ prove that: $$(f\cdot g)^{-1} = f\cdot g^{-1}$$ Any function with the -1 as exponent is the ...
1
vote
1answer
38 views

Finding which base number given operations

$$ (35_a + 24_a) * 21_a = 1081_a $$ Which base is the above number? Any advice on how to solve questions like these? I tried making it in to a polynomial: $(3a+5 + 2a+4) * (2a+1) = 108a + 1$ ...
2
votes
1answer
33 views

How to show this equality

If $f$ is a multiplicative function and ¨$n$¨ is a square-free positive integer. Prove that: $$f^{-1}(n) = \lambda(n)\cdot f(n)$$ where $f^{-1}$ is the dirichlet inverse and $\lambda$ is the ...
0
votes
0answers
40 views

Positive integers of sum and products

Find all pairs of positive integers $m$ and $n$ where $m<n$ such that the sum of $m$ and $n$ added to the product of $m$ and $n$ is equal to $2014$ I just thought about this question and ...
0
votes
3answers
50 views

If $a-b$ is a multiple of $c$, then $a^n - b^n$ is a multiple of $c$

So I'm stuck doing this problem. Since we have to use induction, I have gotten as far as the base step and then realized that I'm going about this wrong. Here's the problem: If $a, b, c \in ...
0
votes
2answers
50 views

Pair of positive integers in product sums

I am still not sure on this answer. I would like someone to help me see the solution to his question. I was working on it for a while and it is the only question that I looked at that I can not ...
4
votes
3answers
124 views

A conjecture on products/composition of Pell forms

Based on a few brute-force calculations, I've formulated the following. Conjecture. Let $x,y,u,v,p,q,a,b,c \ge 2$ be integers such that $$ (x^2+ay^2)(u^2+bv^2) = p^2+cq^2, $$ and write \begin{align} ...
1
vote
4answers
74 views

Prove if $2\mid(x^2-1) $, then $4\mid(x^2-1)$

I have no idea where to start. Any hint(s) or suggestions? Prove if $2\mid(x^2-1) $, then $4\mid(x^2-1)$
0
votes
0answers
10 views

Spectrum sequences problem

I need to prove that if $\alpha \neq \beta$, then the spectrum sequence of $\alpha$ is different from the spectrum sequence of $\beta$ My professor said that you would have to consider two cases: if ...
0
votes
1answer
48 views

Pell's equation for n=2

If know that $x=3$, $y=2$ is a solution of $$x^2-2y^2=1,$$ then apparently all other solutions can be calculated as $$x_k+y_k\sqrt{2}=(x+y\sqrt{2})^k,$$ which I have trouble understanding. I've been ...
4
votes
1answer
45 views

Is it true that the gcd of cubes is the cube of gcd?

Is it true that $\forall a,b\in \mathbb{Z}$, $\gcd(a^3, b^3)=\gcd(a,b)^3$? I cannot find a counterexample, nor have I been able to finish a proof. One thing I tried was: $\gcd(a^3, b^3)= \gcd(a^3, ...
0
votes
2answers
35 views

Divisors of numbers of the form $a^2+2b^2$ with $\gcd(a,b)=1$

Let's say I have a number $n$ which can be written as $a^2+2b^2$ for integers $a,b$. By Fermat/Euler/etc., I know that the primes dividing the squarefree kernel of $n$ cannot be congruent to $5$ or ...
1
vote
1answer
28 views

Rational solutions to a system of equations

I have a system of equations $$\begin{align} xy + 3zw = 0; \\ xz + 2yw = 0; \\ xw + yz = 0. \\ \end{align}$$ Plugging it into a CAS, I see that all the rational solutions to this system have ...