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

learn more… | top users | synonyms (1)

2
votes
2answers
14 views

A question about Quadratic residues and modulos

I need help in understanding why : If a is a Quadratic residue modulo $p^l$ ( $\exists x$ such that $x^2 \equiv a \mod(p^l)$ ) then its a Quadratic residue modulo p ($ \exists x$ such that $x^2 \...
1
vote
6answers
81 views

Finding the unit digit [on hold]

How can I find the unit digit of $2 ^{9^{100}}$. Is there any general method of finding the unit digit?
0
votes
2answers
39 views

Compute $5^{15}$ mod $7$ using the fact that if gcd$(a,n) = 1$, then $a^{\phi(n)}$ mod $n$ = $1$ (Euler-phi function).

Compute $5^{15}$ mod $7$ using the fact that if gcd$(a,n) = 1$, then $a^{\phi(n)}$ mod $n$ = $1$ (Euler-phi function). I see that $5^{15} = 5^{6}5^{6}5^{3} = 5^{\phi(n)}5^{\phi(n)}5^{3}$, but I'm not ...
2
votes
1answer
74 views

There are infinitely many numbers that can't be written as a sum of a prime and a triangular number

While having lunch in our cafeteria, some mathematicians told me of a quite interesting problem: There are infinitely many numbers that can't be written as a sum of a prime and a triangular number. ...
0
votes
2answers
74 views

For all $x$ , $x^2 \equiv 0$ or $1$ or $4 \mod 7$

My textbook makes the following claim For any $x$ , $x^2 \equiv 0$ or $1$ or $4 \mod 7$ I can't see how this true though. $3^2 \equiv 4^2 \equiv 2 \mod 7$ so this obviously doesn't fall into ...
0
votes
0answers
35 views

congruences: number theory

We have the following Diophantine equation on l, m, n(all belong to natural number) $$(4a^2 - y^2)^l + (4ay)^m = (4a^2 + y^2)^n,$$ where a, y both belong to natural number with (a, y) = 1, 2a > 1, y ...
-1
votes
0answers
17 views

number theory: congruences [on hold]

if a is odd, m is congruent to n (mod 2) and m is mot equal to 1. This implies that n is even. How it happens? Given equation is (4a^2 - y^2)^l + (4ay)^m = (4a^2 + y^2)^n where a, y belong to natural ...
2
votes
3answers
69 views

Finding GCD of $95$ and $39$

My Algebra instructor gave us this problem which is to find gcd of $95$ and $39$ and express it as $95x+39y$. Also are $x$, $y$ unique? Now they are relatively prime so GCD is $1$. I have no clue ...
5
votes
4answers
1k views

Proving $ \phi(mn)=\phi(m)\phi(n) \frac k{\phi(k)}$

Suppose $m,n \in \Bbb N$, $k$ is product of all prime number such that divide $m,n$ How to prove that: $$ \phi(mn)=\phi(m)\phi(n) \frac k{\phi(k)}$$
2
votes
6answers
84 views

Prove by induction that $a^{4n+1}-a$ is divisible by 30 for any a and $n\ge1$

It is valid for n=1, and if I assume that $a^{4n+1}-a=30k$ for some n and continue from there with $a^{4n+5}-a=30k=>a^4a^{4n+1}-a$ then I try to write this in the form of $a^4(a^{4n+1}-a)-X$ so I ...
-1
votes
2answers
64 views

Let $A=\{1,2,3,…,2^n\}$. Consider the greatest odd factor of each element of A and add them… [on hold]

Let $A=\{1,2,3,...,2^n\}$. Consider the greatest odd factor (not necessarily prime) of each element of A and add them. What does this sum equal?
6
votes
0answers
54 views

An observation regarding the divisors of Euler's totient function

I observed that if $n$ is a composite number of the form $6k + 1$ then there are at least three divisors of $n - 1$ which do not divide $\phi(n)$ (Euler's totient function). Is this true in general?
5
votes
3answers
63 views

Find $2$ to the power $p^2-1$ modulo $p$

Given a prime number $p>2$, find $2^{p^2-1}$ modulo $p$. I know Fermat's and Euler's theorem but I can't apply them here. Any help would be grateful.
2
votes
2answers
61 views

$2^{n!}\bmod n$ if $n$ is odd

Given an odd number $n$, find $2^{n!}\bmod n$ and what if $n$ is even? I am not getting how to deal with that $n!$ in the power of $2$. Any help will be truly appreciated.....
1
vote
2answers
91 views

How many zeros are there in $25!$? [duplicate]

How many zeros are there in $25!$? I don't know how to really calculate it the number of zeros in the right hand can easily find by Legendre's formula. That gives us: $\lfloor{\frac{25}{5}}\rfloor+\...
0
votes
0answers
34 views

New Criterion to Carmichael Numbers

Can anyone prove the following: If $p$ $=$ $a*b*c$ is a Carmichael Number, and the lcm (least common multiple) of ($a-1$), ($b-1$), and ($c-1$) is $m$, prove ($p-1$)/$m$ is prime. (This applies to ...
2
votes
1answer
68 views

Riemann Hypothesis and $\sum\limits_{k\leq n}\left(\frac{\mu(k)}{k}\right)^2$

I know that Riemann Hypothesis is equivalent to the following statement $\sum\limits_{k\leq n}\frac{\mu(k)}{k}=O(n^{-1/2+\epsilon})$ Is there any relation between Riemann Hypothesis and $\sum\...
0
votes
1answer
25 views

Is it possible to predict the digit sum of two factors by the product's digit sum?

Let's say we have a number that is the product of exactly two prime numbers, for example: 143 = 11*13 The digit sum of the product correlates with the digit sum of the factors: Digit sums: DS(...
20
votes
4answers
3k views

Can a finite sum of square roots be an integer?

Can a sum of a finite number of square roots of integers be an integer? If yes can a sum of two square roots of integers be an integer? The square roots need to be irrational.
0
votes
1answer
30 views

Prove that $n^7$ = n(mod 42) [duplicate]

We have to prove $n^7$ = n(mod 42) i tried as We know $n^7$-n is divisible by 7 Hence n(n-1)(n+1)(n$^2$ +1 +n) is divisible by 7
1
vote
2answers
58 views

If $a$ and $b$ are whole numbers from $1$ to $100$, how many pairs of numbers $(a,b)$ are there which satisfy $a^{\sqrt{b}}=\sqrt{a^b}$

If $a$ and $b$ are whole numbers from $1$ to $100$, how many pairs of numbers $(a,b)$ are there which satisfy $a^{\sqrt{b}}=\sqrt{a^b}$ This was from a math contest I did earlier today and I was ...
1
vote
0answers
31 views

Concerning Arithmetic Progressions

Let p and q be two consecutive prime numbers. Let there be two arithmetic progressions whose initial terms differ by 2. Let both arithmetic progressions have the same common difference. Let the ...
5
votes
1answer
98 views

Factoring $a^2+b^2$?

I remember there was a way to factor $a^2+b^2$ into something along the lines of $(a+\sqrt{a}+b)(a-\sqrt{a}+b)$ . I tried every combination of pluses and minuses for this form, but I couldn't get back ...
0
votes
1answer
27 views

How can you solve this type of (not quite linear) diophantine equation in 2 variables?

Is there a general technique to find solutions of this type of equation? 555555=t+2rt+r I'll provide the only answer I know in the comments. Thanks.
-1
votes
0answers
16 views

Proof that a binary adder can be used to perform an n-bit unsigned subtraction

A n-bit binary adder can be used to perform an n-bit unsigned subtraction operation $X - Y$, by performing the operation $X + Y + 1$, where $X$ and $Y$ are n-bit unsigned numbers and $Y$ (with a bar) ...
3
votes
1answer
1k views

IMO 2016 Problem 3

Let $P = A_1 A_2 \cdots A_k$ be a convex polygon in the plane. The vertices $A_1, A_2, \ldots, A_k$ have integral coordinates and lie on a circle. Let $S$ be the area of $P$. An odd positive integer $...
1
vote
0answers
37 views

How to find the first integer making two progressions have gcd $> 1$

Is there a technique to efficiently find the first positive integer, $r$, that makes: $$\gcd(97+r, 106-r) > 1\text{?}$$
1
vote
1answer
30 views

Locating the double of a number in a triangular arrangement of the integers?

I write the positive numbers starting at $1$ in a triangle:$$\mathbb{N}_\triangle = \begin{matrix} &&&&&21&\ldots \\ &&&&15&20&\ldots ...
7
votes
5answers
195 views

Disprove that “if $p$ is a prime number, then $2^p-1$ is also a prime number”?

We can see manually that $2^p-1$ is not prime. As $2047$ is not a prime. $2^{11} = 2048$. But I'm unable to figure out a formal way of disproving the statement.
-4
votes
0answers
53 views

The smallest even/odd integers such that $\sum_{k=1}^nk$ is a square

Let m be the smallest odd positive integer for which 1 + 2 + ··· + m is a square of an integer and let n be the smallest even positive integer for which 1 + 2 + ··· + n is a square of an integer. What ...
-3
votes
0answers
39 views

Any prime number $(p)$, in sequence $(p^n, p^n+1…)$. Each term in sequence is divisible only for previous terms? [on hold]

Any prime number $(p)$, in sequence $(p^n, p^{n+1}, p^{n+2},...)$. Each term in sequence is divisible only by previous terms? This is relevant or simple derivation?
1
vote
2answers
90 views

Solve the equation $1-x+x^{2}-x^{3}+x^{4}=y^{4}$ in $\mathbb{Z}$

I am working on the following exercise. Solve the equation $1-x+x^{2}-x^{3}+x^{4}=y^{4}$ in $\mathbb{Z}$. I have a couple of ideas for going about this exercise. $1)$ By moving $1$ to the other side ...
1
vote
3answers
180 views

Is “$x^2=1\implies x=\pm 1$” true on any field? why?

The only elements $x\in\Bbb F_p$ with $x^2=1$ are $\pm1$, right? Is that true for any field? How do I see that it's true?
1
vote
0answers
35 views

How often is $k, 2k, 3k…$ modulo $n$ less than $b$ before it hits $-1$?

Let $n$ and $k$ be coprime, and let $1\leq b \leq n$. The sequence $k, 2k ,3k, \ldots$ reduced modulo $n$ to the range $1, \ldots, n$, will eventually run through every integer in the range $1, \ldots,...
5
votes
0answers
58 views

Interesting property of Fibonacci numbers

Let we have an integer number $m$ such that $p \mid m \implies (p^2-1) \mid m$ for any prime divisor $p$ of $m.$ Prove that for such $m$ we have $F_{n+m}=F_{m} \mod m $ for any $n>1.$ Any ideas ...
2
votes
2answers
61 views

year 10 factorial question

I would like to know the number of zeros occuring in the factorial of 2016? (2016!) I have read some ways but i don't understand it.
0
votes
2answers
74 views
1
vote
2answers
62 views

“if $n$ is a composite integer, then $n$ has a prime factor not exceeding ${\sqrt n}$” - proof explanation

the proof of this theorem was as follows: since $n$ is composite, then $n=ab$, where $a$ and $b$ are integers with $1\lt a \le b \lt n$. Suppose now that $a \gt {\sqrt n}$, then $${\sqrt n} \lt a \...
3
votes
4answers
44 views

On the kernel of a certain module epimorphism $\mathbb{Z}^2 \to \mathbb{Z}/6\mathbb{Z}$

In order the construct a certain projective resolution of $\mathbb Z / 6 \mathbb Z$ I need to find the kernel of the ($\mathbb Z$-) module morphism: $$\epsilon_0 : \mathbb Z^2 \to \mathbb Z / 6 \...
0
votes
2answers
27 views

Can the set of uneven number be written as the intersection of two sets?

Let $U = \{ n \in \mathbb{N} | n \equiv 1 (2) \}$. My question is: Can we find two proper subsets $M,N$ of $\mathbb{N}$ such that $M \neq N$ and $M,N$ are not equal to $U$ and $U = M \cap N$? It ...
-2
votes
0answers
27 views

Combinatorical problem [on hold]

$k$ is a natural constant.Determine $x,y,z$ knowing that $\binom{z+k}{x+y} + \binom{z}{x} \le k$ and $2x+y \le z$.
-3
votes
0answers
34 views

Comp Questions-Enumeration, Rates, Numbers, Geometry [on hold]

For each integer from 0 to 999, Michael wrote down the sum of its digits. What is the average of the numbers that Michael wrote down? It takes Jacob one and a half hours to paint the walls of a room ...
7
votes
3answers
137 views

Number of integer triplets $(a,b,c)$ such that $a<b<c$ and $a+b+c=n$

What is an equivalent combinatorial presentation for the problem? Can I use the stars and bars approach to find the number of integral solutions of $a+b+c=n$ where $a,b,c\geq 0$? If in addition $a+b&...
3
votes
1answer
587 views

How to prove a generalized Gauss sum formula

I read the wikipedia article on quadratic Gauss sum. link First let me write a definition of a generalized Gauss sum. Let $G(a, c)= \sum_{n=0}^{c-1}\exp (\frac{an^2}{c})$, where $a$ and $c$ are ...
2
votes
2answers
251 views

Integer solutions of $xy+9(x+y)=2006$

How many integer solutions does $xy+9(x+y)=2006$ have? Here $x$ and $y$ are both integers. My trying: I have tried to solve this problem. But I have no idea to solve this. Please help
0
votes
2answers
43 views

Proving Fermat's Little Theorem with Lagrange

I know how to prove Fermat's little theorem using the binomial expansion and induction. How can I prove it using Lagrange's theorem? So I want to show $c^p\equiv c\pmod p$, i.e. $c^{p-1}\equiv 1\...
4
votes
1answer
115 views

For which values of $n$ the sum $\sum_{k=1}^n k^2$ is a perfect square?

Question. For which values of $n$ the sum $\sum_{k=1}^n k^2$ is a perfect square? Clearly, $n=24$ is one such value, and I was wondering whether this is the only value for which the above holds. The ...
4
votes
7answers
103 views

Prove that $p^2 - 4qr$ ($p,q,r$ odd natural numbers) is never a perfect square

The givens for the question: $p, q, r$ are odd natural numbers. We need to prove that $p^2 - 4qr$ is never a perfect square. Inspecting a few examples it seems to be true, but I have no idea where to ...
1
vote
7answers
191 views

Prove that ${2^n-1\choose k}$ and ${2^n-k\choose k}$ ar always odd. [duplicate]

How can I prove that ${2^n-1\choose k}$ and ${2^n-k\choose k}$ always returns odd numbers? It is possible to prove this by congruence? by the way : $0 \leq k \leq (2^n-1)$
0
votes
1answer
126 views

Find integer solutions

Find all integer solutions to the following: $2x+10y-11z=1$ $x-6y+14z=2$ I am not quite sure how to do this... I know I will get equations in the end with each variable expressed in terms of ...