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

learn more… | top users | synonyms

1
vote
0answers
12 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
27 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
20 views

Force non-consecutive colours for 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 ...
12
votes
5answers
516 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
43 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
22 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
39 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
32 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
25 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
43 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
45 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 ?
0
votes
1answer
64 views

Cut squares from sheet

A rectangular paper sheet of M*N is to be cut down into squares. ...
0
votes
2answers
32 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
18 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 ...
1
vote
0answers
52 views

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
26 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
57 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 ...
0
votes
0answers
27 views

Where is the Mistake in My Approach?

Using Pick's Theorem we will be trying to find the expression for the value of Legendre Symbol. To be specific, we will try to calculate the value of $\left(\dfrac{q}{p}\right)$ where both $q$ and $p$ ...
0
votes
7answers
77 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
20 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
43 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
8 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
16 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 ...
6
votes
3answers
430 views

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

How many ways are there to write 675 as a difference of two squares? Is there a way to generalize this?
2
votes
2answers
41 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
93 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
44 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
49 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
49 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 ...
3
votes
2answers
97 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
72 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
9 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
44 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
26 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 ...
-1
votes
0answers
27 views

Find no. of pair of (i,j).

The number of pairs of (i,j) which satisfy the condition (2^j-1) mod (2^i-1) = 0 where the 1 <= i < j <= n ; n is the number under which number of (i,j) pairs are to be found.
0
votes
1answer
27 views

Number of Lattice Points in a Triangle

Problem Let the co-ordinates of the vertices of the $\triangle OAB$ be $O(1,1)$, $A(\frac{a+1}{2},1)$ and $B(\frac{a+1}{2},\frac{b+1}{2})$ where $a$ and $b$ are mutually prime odd integers, ...
0
votes
0answers
29 views

How can I solve equations involving modulo both side like this one?

I need to find $x \bmod m$ from the below equation: $$((p \bmod m)(x \bmod m)) \bmod m \equiv q\bmod m$$
0
votes
1answer
28 views

if $k>1$, Does $a+b =k(ax+by)$ have finitely many solutions?

Let $a,b,k,x,y$ be non-zero integers, solve $a+b=k(ax+by)$. It's a rather simple problem, but I just want to make sure that I have got all the possible solutions.
0
votes
0answers
31 views

Proving spectrum sequences are different

I am trying to prove that if $\alpha \neq \beta$, then the spectrum sequence of $\alpha$ is different from the spectrum sequence of $\beta$. I have that the spectrum sequence of a real number ...
1
vote
1answer
40 views

Finding pair of integers with given modulo

Given integer Goal and S = { X0, X1, ...., Xn } where Xi is a positive integer > 1, find a, b, in S and positive integer n (not necessarily in S) such that: a*n mod b = Goal E.g. Goal = 1, S = {3, ...
0
votes
1answer
27 views

Form of solutions of Diophantine equation

Consider the following Diophantine equation $$zx^2 +xy^2 +yz^2 =xyzt .$$ Is that true that all solutions of this equation are of the form $(x,y,z,t) =(a^2 b ,b^2 c ,c^2 a ,t)$ for some ...