Tagged Questions

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

learn more… | top users | synonyms

1
vote
1answer
564 views

Modulus Distributing Over Multiplication?

Given positive integers a,b,c and k: Define a function $M: \mathbb{Z^2} \rightarrow \mathbb{Z}$ as $$M(x,y) = (x \bmod y)$$ i.e. the remainder of integer division The following is always true: ...
0
votes
1answer
39 views

Sum of mutliples b/w $2$ and $10$ . What is wrong with this method

I am trying to find the sum of multiples b/w $2$ and $10$ end points non-inclusive using the following mechanism and I don't know why I am getting the wrong answer. (I selected this small range ...
2
votes
4answers
114 views

Are the two statements concening number theory correct?

Statement 1: any integer no less than four can be factorized as a linear combination of two and three. Statement 2: any integer no less than six can be factorized as a linear combination of three, ...
9
votes
4answers
3k views

Is there a way to determine how many digits a power of 2 will contain?

Is there a direct way to determine how many digits a power of 2 will contain without actually performing the multiplication? An estimation would help as well if there is no absolute solution. EDIT: ...
1
vote
1answer
106 views

prove existence of integers $a,q$ which satisfy the following inequality

Let $x \in \mathbb{R}$ and integer $Q \geq 1$. Prove: there exist integers $a$ and $1 \leq q \leq Q$ such that $|x - \frac aq | < \frac 1{qQ} $ any help would be appreciated!
0
votes
1answer
141 views

Which value is greater ? Sum of same four numbers or 36

I came across the following question The average of four numbers is 36. Which is greater Sum of same four numbers or $140$ Now the answer states (a- The sum of same four numbers). How ...
1
vote
5answers
862 views

Minimum value of $x+y$ when $xy=36$

How would I calculate minimum value of $x+y$ when $xy=36$ and x and y are unequal positive integer numbers. I don't even know the answer. Any help would be appreciated. Edit: Sorry It was the ...
1
vote
4answers
1k views

What digit appears in unit place when $2^{320}$ is multiplied out

Is there a way to answer the following preferably without a calculator What digit appears in unit place when $2^{320}$ is multiplied out ? a)$0$ b)$2$ c)$4$ d)$6$ e)$8$ ---- Ans(d)
4
votes
3answers
277 views

Properties and identities of $\text{ord}_{p}(n)$

$\mathrm{ord}_{p}(a+b)\ge\mathrm{min}(\mathrm{ord}_{p}a,\mathrm{ord}_{p}b)$ with equality holding if $\mathrm{ord}_{p}a\ne \mathrm{ord}_{p}b$. is a the statement that prompted this question. It was ...
1
vote
4answers
974 views

What is smallest possible integer k such that $1575 \times k$ is perfect square?

I wanted to know how to solve this question: What is smallest possible integer $k$ such that $1575 \times k$ is a perfect square? a) 7, b) 9, c) 15, d) 25, e) 63. The answer is 7. ...
1
vote
4answers
1k views

How many int. values of n will the expression be greater than 1

How would I solve this problem: How many integer values of n will the expression $4n+7$ be an integer greater than 1 and less than 200 a)48 b)49 c)50 d)51 e)52 ? Ans 50 I am trying to ...
4
votes
1answer
75 views

Number of combinations of sets over a function.

Does anyone know if the following question has been solved in general or has any insight in the question. Let us take for example the sets {0,1} and {1,2} and function multiplication (*) over the ...
5
votes
2answers
323 views

Why does the $2$'s and $1$'s complement subtraction works?

The algorithm for $2$'s complement and $1$'s complement subtraction is tad simple: $1.$ Find the $1$'s or $2$'s complement of the subtrahend. $2.$ Add it with minuend. $3.$ If there is ...
2
votes
2answers
199 views

How to find all solutions to equations like $3x+2y = 380$ using matrices/linear algebra?

I'm coming up blank on Wikipedia and other sources, though this seems elementary. I'd like to know what techniques or processes are used to find all (integer) solutions to an equation such as $3x+2y = ...
5
votes
5answers
2k views

Prove that there do not exist positive integers $x$ and $y$ with $x^2 - y^2 = n$

I'm working on a homework problem that is as follows: Suppose that $n$ is a positive even integer with $n/2$ odd. Prove that there do not exist positive integers $x$ and $y$ with $x^2 - y^2 = n$. ...
1
vote
1answer
73 views

If $(m_1,m_2)=D$, $(a,m_1)=d_1$, $(b,m_2)=d_2$, then $(am_2+bm_1, m_1m_2)=?$

We know, If $(m_1,m_2)=(a,m_1)=(b,m_2)=1, \iff (am_2+bm_1, m_1m_2)=1$ I tried to generalize now. Let $(a,m_1)=d_1, (b,m_2)=d_2$ where $d_1,d_2$ need not to be 1. $(am_2+bm_1, m_1m_2)$ ...
3
votes
0answers
137 views

Prove: $\frac{(2px)!}{((px)!)^2}\equiv\frac{(2x)!}{((x)!)^2}\pmod{p^2}$

How can I prove the following, where $p$ is a prime and $x$ a positive integer? $$\dfrac{(2px)!}{((px)!)^2}\equiv\dfrac{(2x)!}{((x)!)^2}\pmod{p^2}$$ I'm not sure if it is actually true, but I tested ...
2
votes
3answers
113 views

Proving that if $p$, $q$ are rationals and $p < q$, then there is a rational $v$ such that $p < v < q$

The question itself looks pretty simple, but I'm a complete beginner and have no idea where to start. Any help would be greatly appreciated Proving that if $p$, $q$ are rationals and $p < q$, then ...
2
votes
3answers
2k views

Proving that for each prime number $p$, the number $\sqrt{p}$ is irrational [duplicate]

Possible Duplicate: $\sqrt a$ is either an integer or an irrational number. I'm a total beginner and any help with this proof would be much appreciated. Not even sure where to begin. ...
3
votes
1answer
152 views

What is the highest power of $n$ in $(n^r-1)!$

What is the highest power of n in $(n^r-1)!$ where $n$, $r$ are positive integers? The answer supplied is $\frac{n^r-nr+r-1}{n-1}$ The highest power of $n$ in $n^r! = r +$ the highest power of $n$ ...
2
votes
2answers
130 views

How many elements $a \in \Bbb{Z}_N$ such that $ax \equiv y \mod N$

Consider the ring $\Bbb{Z}_N$ of arithmetic modulo $N$: $\{0,1,2, \ldots ,N-1\}.$ Given $x,y \in \Bbb{Z}_N,$ how many of the elements of $\Bbb{Z}_N$ when multiplied with $x \pmod{N}$ result in $y$? ...
3
votes
9answers
205 views

If both $a$ and $b$ $\not \equiv 0 \pmod{p}$ then $ab \not\equiv 0 \pmod{p}$

Any help with this proof would be great. Not even sure where to begin. I'm pretty much a total newbie. If $a$ is not congruent to $0 \pmod{p}$ and $b$ is not congruent to $0 \pmod{p},$ where $p$ ...
0
votes
3answers
213 views

If $p$ is a factor of $m^2$ then $p$ is a factor of $m$

I'm a complete beginner and not sure where to go with this proof of Euclid's lemma. Any help would be greatly appreciated. If $m$ is a positive integer and a prime number $p$ is a factor of $m^2,$ ...
2
votes
3answers
292 views

Is this statement stronger than the Collatz conjecture?

$n$,$k$, $m$, $u$ $\in$ $\Bbb N$; Let's see the following sequence: $x_0=n$; $x_m=3x_{m-1}+1$. I am afraid I am a complete noob, but I cannot (dis)prove that the following implies the ...
1
vote
0answers
103 views

Does the shifting square root method work for non-integer bases?

Under "methods of computing square roots", Wikipedia states that the digit-by-digit calculation method, of which the shifting $n^{th}$ root algorithm is a generalization, works for all bases, but the ...
1
vote
1answer
284 views

Convergence of a series of reciprocal prime numbers

If $p$ is a prime number, and $q$ is its twin prime, the sum of the reciprocal twin numbers is convergent and the value of the sum of the series is the Brun constant. Now, if we consider the prime ...
1
vote
2answers
72 views

A Trivial Question - Increasing by doubling a number when its negative

The question is : if $x=y-\frac{50}{y}$ , where x and y are both > $0$ . If the value of y is doubled in the equation above the value of x will a)Decrease b)remain same c)increase four fold ...
1
vote
0answers
52 views

Minimal fractional representation in $\Bbb Z/p\Bbb Z$

I arrived to needing an algorithm for the following subproblem while solving a more complex problem. It seems it should be a very standard algorithm, but my number theory isn't too fresh so I haven't ...
0
votes
1answer
85 views

Largest positive integer $k$ such that $\mu(n+r)=0$ for all $1\leq r\leq k$

Find the largest positive integer $k$, such that $\mu(n+r)=0$ for all $1\leq r\leq k$ where $r,n$ are positive integers. As far as I could make out, we need to find out the maximum range(if nay) ...
7
votes
3answers
266 views

Solving simple congruences by hand

When I am faced with a simple linear congruence such as $$9x \equiv 7 \pmod{13}$$ and I am working without any calculating aid handy, I tend to do something like the following: "Notice" that adding ...
17
votes
2answers
608 views

Multiplication tables with all entries distinct

Let positive integers $\alpha$ and $\beta$ be given. It is easy to find sets $A$ and $B$ of positive integers such that: $|A|=\alpha$ and $|B|=\beta$ The set $P = \{ab : a\in A, b\in B\}$ contains ...
1
vote
1answer
114 views

What values can $n$ assume, when $z^2+n= x^2+y^2$?

$x^2+y^2 =n +z^2$ where $x,y,z$ are different natural numbers. What values can $n$ assume? What if x,y,z>0 considering the confusion of 0 as natural number?
6
votes
8answers
392 views

Divisibility of composite numbers

I am having difficulty in solving following types of problem: Sometimes we are given a number in terms of $n$ and we have to check whether it is divisible by a particular composite number. For ...
0
votes
3answers
145 views

Given that $5n$ is a square and $75np$ is a cube, why is the smallest possible value of $n+p$ equal to $14$?

I can't solve this problem: Suppose $n$ and $p$ are integers greater than $1$, $5n$ is the square of a number, and $75np$ is the cube of a number. What is the smallest value for $n+p$? ...
2
votes
3answers
95 views

The square of every integer is of the form either $3k+1$ or $3k$

How can I prove that square of every integer is of the form either $3k+1$ or $3k$, but not $3k+2$? My approach I considered first, the integer $n$ to be even and then $n= 2m$; and if $n$ is odd ...
0
votes
2answers
107 views

Average of numbers in a specific range

The question is : What is the arithmetic mean of all multiples of 10 from 10 to 190 inclusive. Now I know how many nos there are by using $\frac{190-10}{10}+1 = 19$ but how do I get ...
2
votes
1answer
436 views

A power-exponential congruence equation

Let $n \in \mathbb{N}$ with $(n,\varphi(n))=1$ , where $\varphi$ is the Euler-totient function. Prove the equation $x^x \equiv c \pmod{n}$ has integer solution for all $c \in \mathbb{N}$ My thought: ...
3
votes
1answer
358 views

How to efficiently compute the order of a prime number mod $l$ [duplicate]

Possible Duplicate: Quick algorithm for computing orders mod n? Let $l$ be an odd prime number. Let $p$ be a prime number such that $p \neq l$. I'd like to compute efficiently the order of ...
4
votes
1answer
124 views

If $A,B$ are factors of $2^6 3^4 5^2,$ how many values of $|A-B|$ are possible?

Let $x=2^6 3^4 5^2$, then how many distinct values of $|A-B|$ are possible where $A, B$ are the factors of $x$? How to approach this problem?
3
votes
1answer
158 views

Integers of the form $a^2+b^2+c^3+d^3$

It's easy$^*$ to prove that if $n=3^{6m}(3k \pm 1)$ where $(m,k) \in \mathbb{N} \times \mathbb{Z}$, then $n=a^2+b^2+c^3+d^3$ with $(a,b,c,d) \in \mathbb{Z}^4$. But how to prove that this is true if ...
1
vote
2answers
118 views

Unique number for multiplication

I am looking for a number that when multiplied by any number and divided by 10000 never leaves the 3 digit number as 291 , I mean I am looking for a number that leaves a remainder as 1231 , 1001 ...
0
votes
1answer
663 views

Cyclotomic polynomial over a finite prime field [duplicate]

Possible Duplicate: Irreducible factors of $X^p-1$ in $(\mathbb{Z}/q \mathbb{Z})\[X\]$ Let $p$ be a prime number. Let $l$ be an odd prime number such that $l \neq p$. Let $X^l - 1 \in ...
2
votes
3answers
607 views

16 digit numbers divisible by 17

I wanted to know about the $16$ digit numbers those are divisible by $17$ and when this $16$ digit number is broken in groups of $4$ those groups of four are also divisible by $17$ and a check to ...
6
votes
1answer
136 views

Is there a name for the “most square” factorization of an integer?

For the definition that follows, I'm curious to know if there's a known name (to enable a literature search relating to algorithms). Definition. Given an integer $n$, the maximally square ...
7
votes
5answers
670 views

Finding the divisors of a number

My text says that $p^3q^6$ has 28 divisors. Could anyone please explain to me how they got 28 here ? Edit: $p$ and $q$ are distinct prime numbers Sorry for the late addition..
1
vote
1answer
230 views

How does this game work? (Number game: subtract prime)

Problem Alice and Bob play the following game.They choose a number N to play with.The runs are as follows : 1.Bob plays first and the two players alternate. 2.In his/her turn ,a ...
2
votes
1answer
135 views

Farey sequences for polynomials?

Does a notion of Farey sequence (or something equivalent) exist for polynomials over finite fields?
1
vote
1answer
70 views

checking whether certain numbers have an integral square root

I was wondering if it is possible to find out all $n \geq 1$, such that $3n^2+2n$ has an integral square root, that is, there exists $a \in \mathbb{N}$ such that $3n^2+2n = a^2$ Also, similarly for ...
0
votes
0answers
127 views

When can $a^m-b^m$ divide $a^m+b^m$. where $a$, $b$, $m$ are natural numbers, $a\gt b$

When can $(a^m-b^m)$ divide $(a^m+b^m)$, where $a$, $b$, $m$ are natural numbers, $a \gt b$. I approached this way: Let $(a,b)=d$ and $\frac{a}{A}=\frac{b}{B}=d$, so $(A,B)=1$ and $A>B$. ...
1
vote
1answer
99 views

Solving Congruences and CRT

I have never really directly dealt with congruences until I was introduced to the Chinese Remainder Theorem. Although there are tons of different versions of this theorem out there, currently I am ...